Apa perbedaan antara NP-keras dan NP-lengkap?

Suatu masalah adalah NP-keras jika setiap masalah NP dapat direduksi kepadanya dalam waktu polinomial, tetapi masalah itu sendiri tidak harus berada dalam NP dan tidak harus menjadi masalah keputusan. Suatu masalah adalah NP-lengkap jika masalah tersebut NP-keras dan juga berada dalam NP. Masalah NP-lengkap adalah masalah tersulit yang masih berada dalam NP.

Apakah NP-kelengkapan berarti suatu masalah tidak akan pernah bisa dipecahkan?

Tidak. Ini berarti tidak ada algoritma waktu polinomial yang diketahui untuk semua masukan dan kemungkinan besar tidak ada jika P tidak sama dengan NP. Dalam praktiknya, masalah-masalah semacam itu ditangani dengan algoritma aproksimasi, heuristik, pemecah waktu eksponensial yang bekerja pada instans realistis, atau dengan membatasi pada kasus-kasus khusus.

NP-Kelengkapan dan Intractability

NP-kelengkapan mengidentifikasi masalah-masalah tersulit dalam kelas NP — yaitu masalah-masalah yang setiap masalah NP dapat direduksi kepadanya — dan menyediakan kerangka kerja standar untuk mengenali masalah-masalah yang belum atau kemungkinan besar tidak memiliki algoritma efisien.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Masalah keputusan adalah NP-lengkap jika masalah tersebut berada dalam NP (instansinya yang 'ya' memiliki sertifikat yang dapat diverifikasi secara efisien) dan setiap masalah dalam NP dapat direduksi kepadanya dalam waktu polinomial; masalah-masalah semacam itu adalah yang tersulit dalam NP, dan algoritma waktu polinomial untuk salah satunya akan menghasilkan algoritma untuk semuanya.

Scope

Topik ini mencakup kelas kompleksitas P dan NP, reduksi waktu polinomial, definisi NP-kekerasan (NP-hardness) dan NP-kelengkapan (NP-completeness), teorema Cook-Levin yang menetapkan kepuasan (satisfiability) sebagai NP-lengkap, katalog masalah NP-lengkap Karp, dan konsekuensi praktis dari intractability untuk desain algoritma. Ini menerapkan konsep-konsep ini untuk mengenali dan mengatasi masalah-masalah sulit; teori formal yang lebih luas tentang kelas kompleksitas komputasi dibahas dalam subbidang teori komputasi.

Core questions

Apa yang membedakan kelas kompleksitas P dan NP?
Bagaimana reduksi waktu polinomial mentransfer kesulitan dari satu masalah ke masalah lain?
Apa yang ditetapkan oleh teorema Cook-Levin, dan mengapa kepuasan (satisfiability) menjadi pusatnya?
Bagaimana masalah baru dibuktikan NP-lengkap melalui reduksi dari masalah yang sudah diketahui?
Setelah suatu masalah terbukti NP-keras, strategi algoritmik apa yang tersisa?

Key concepts

kelas kompleksitas P
kelas kompleksitas NP
reduksi waktu polinomial
NP-kekerasan (NP-hardness)
NP-kelengkapan (NP-completeness)
teorema Cook-Levin
kepuasan Boolean (SAT)
masalah P versus NP

Key theories

Teorema Cook-Levin: Teorema Cook-Levin membuktikan bahwa kepuasan Boolean (SAT) adalah NP-lengkap: setiap masalah dalam NP dapat direduksi kepadanya dalam waktu polinomial, menyediakan masalah NP-lengkap pertama dan jangkar untuk membuktikan masalah lain sulit.
Reduktabilitas di antara masalah kombinatorial: Karp menunjukkan bahwa reduksi waktu polinomial menghubungkan banyak masalah alami — clique, vertex cover, siklus Hamiltonian, partisi, dan lainnya — ke dalam jaringan masalah NP-lengkap, sehingga masing-masing dapat dibuktikan sulit melalui reduksi dari yang lain.

Clinical relevance

Mengenali bahwa suatu masalah adalah NP-lengkap merupakan salah satu hasil yang paling berguna secara praktis dalam komputasi: hal ini memberi tahu para insinyur untuk tidak mengharapkan algoritma eksak yang cepat dan sebaliknya menggunakan algoritma aproksimasi, heuristik, pemecah eksak yang disesuaikan untuk instans tipikal, atau pembatasan pada kasus-kasus khusus yang dapat dipecahkan. Banyak masalah penjadwalan, perutean, pengepakan, dan desain adalah NP-lengkap.

History

Stephen Cook memperkenalkan NP-kelengkapan pada tahun 1971, membuktikan SAT NP-lengkap; Leonid Levin mencapai hasil serupa secara independen. Makalah Richard Karp tahun 1972 menunjukkan 21 masalah alami yang NP-lengkap, menetapkan jangkauan kerangka kerja tersebut. Buku Garey dan Johnson tahun 1979 mengkatalogkan ratusan masalah NP-lengkap dan menjadi referensi standar.

Debates

P versus NP: Apakah P sama dengan NP — apakah setiap masalah yang dapat diverifikasi secara efisien juga dapat dipecahkan secara efisien — adalah masalah terbuka terkemuka di bidang ini; hampir semua peneliti menduga P tidak sama dengan NP, tetapi pertanyaan ini belum terpecahkan dan merupakan masalah Hadiah Milenium.

Key figures

Stephen Cook
Richard Karp
Leonid Levin
Michael Garey
David Johnson

Seminal works

cook1971
karp1972
cormen2009

Frequently asked questions

Apa perbedaan antara NP-keras dan NP-lengkap?: Suatu masalah adalah NP-keras jika setiap masalah NP dapat direduksi kepadanya dalam waktu polinomial, tetapi masalah itu sendiri tidak harus berada dalam NP dan tidak harus menjadi masalah keputusan. Suatu masalah adalah NP-lengkap jika masalah tersebut NP-keras dan juga berada dalam NP. Masalah NP-lengkap adalah masalah tersulit yang masih berada dalam NP.
Apakah NP-kelengkapan berarti suatu masalah tidak akan pernah bisa dipecahkan?: Tidak. Ini berarti tidak ada algoritma waktu polinomial yang diketahui untuk semua masukan dan kemungkinan besar tidak ada jika P tidak sama dengan NP. Dalam praktiknya, masalah-masalah semacam itu ditangani dengan algoritma aproksimasi, heuristik, pemecah waktu eksponensial yang bekerja pada instans realistis, atau dengan membatasi pada kasus-kasus khusus.