NP-Kelengkapan dan Reduksi

Masalah NP-lengkap adalah salah satu yang tersulit dalam kelas NP, dalam artian bahwa setiap masalah NP dapat direduksi kepadanya secara efisien, sehingga menyelesaikan satu masalah NP-lengkap dengan cepat akan menyelesaikan semuanya.

Definition

Suatu masalah dikatakan NP-lengkap jika masalah tersebut berada dalam NP dan setiap masalah dalam NP dapat direduksi kepadanya melalui reduksi waktu polinomial; masalah-masalah semacam itu adalah anggota NP yang paling sulit, setara satu sama lain hingga transformasi yang efisien.

Scope

Topik ini mencakup kelas masalah NP yang dapat diverifikasi dalam waktu polinomial, reduksi banyak-satu waktu polinomial, teorema Cook–Levin yang menetapkan kepuasan (satisfiability) sebagai NP-lengkap, katalog masalah kombinatorial NP-lengkap Karp, dan metodologi pembuktian masalah baru sebagai NP-lengkap melalui reduksi dari masalah yang sudah diketahui.

Core questions

• Apa artinya suatu masalah termasuk yang tersulit dalam NP?
• Bagaimana teorema Cook–Levin mengidentifikasi masalah NP-lengkap pertama?
• Bagaimana reduksi digunakan untuk membuktikan bahwa masalah baru adalah NP-lengkap?
• Mengapa NP-kelengkapan satu masalah memiliki implikasi bagi ribuan masalah lainnya?

Key theories

Teorema Cook–Levin

Kepuasan Boolean (Boolean satisfiability) adalah NP-lengkap karena komputasi verifikator waktu polinomial apa pun dapat dikodekan sebagai instans kepuasan, menyediakan masalah lengkap fundamental dari mana masalah lain diturunkan.

Reduksi Karp dan jaringan masalah NP-lengkap

Karp menunjukkan bahwa dua puluh satu masalah alami, dari pewarnaan graf hingga masalah keputusan pedagang keliling, adalah NP-lengkap melalui reduksi waktu polinomial, meluncurkan praktik penetapan kesulitan melalui jaringan reduksi yang berkembang.

Clinical relevance

NP-kelengkapan adalah diagnostik praktis dari intractability: setelah suatu masalah dalam penjadwalan, logistik, desain, atau verifikasi terbukti NP-lengkap, para insinyur berhenti mencari algoritma eksak yang dijamin cepat dan beralih ke algoritma aproksimasi, heuristik, pemecah pemrograman bilangan bulat, atau pembatasan yang membuat masalah tersebut dapat diatasi.

History

Cook membuktikan kepuasan (satisfiability) sebagai NP-lengkap pada tahun 1971, dan Levin secara independen memperoleh hasil yang setara di Uni Soviet. Pada tahun 1972 Karp mendemonstrasikan dua puluh satu masalah NP-lengkap lainnya, mengungkapkan meluasnya fenomena tersebut dan menjadikan NP-kelengkapan sebagai alat utama untuk mendiagnosis kesulitan komputasi.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

Apa kepanjangan dari NP?

NP berarti waktu polinomial nondeterministik. Secara ekuivalen, suatu masalah berada dalam NP jika solusi yang diusulkan dapat diperiksa dalam waktu polinomial, meskipun menemukannya tampak sulit. Rute pedagang keliling di bawah panjang tertentu mudah diverifikasi setelah diberikan tetapi tampaknya sulit ditemukan.

Bagaimana cara membuktikan bahwa masalah baru adalah NP-lengkap?

Anda menunjukkan dua hal: bahwa masalah tersebut berada dalam NP, sehingga solusi kandidat dapat diperiksa dengan cepat, dan bahwa beberapa masalah NP-lengkap yang diketahui dapat direduksi kepadanya dalam waktu polinomial. Reduksi tersebut mentransfer kesulitan yang diketahui, menempatkan masalah baru di antara yang tersulit dalam NP.