Masalah P versus NP

Masalah P versus NP menanyakan apakah setiap masalah yang solusinya dapat diverifikasi dengan cepat juga dapat diselesaikan dengan cepat, yang merupakan pertanyaan terbuka sentral dalam ilmu komputer teoretis dan salah satu masalah Clay Millennium Prize.

Definition

P adalah kelas masalah yang dapat diselesaikan dalam waktu polinomial, dan NP adalah kelas masalah yang solusi yang diusulkan dapat diverifikasi dalam waktu polinomial; masalah P versus NP menanyakan apakah kedua kelas ini sama, yang berlaku jika dan hanya jika beberapa masalah NP-lengkap dapat diselesaikan dalam waktu polinomial.

Scope

Topik ini mencakup pernyataan formal P versus NP, kesetaraannya dengan apakah ada masalah NP-lengkap yang memiliki algoritma waktu polinomial, konsekuensi dari salah satu jawaban, hambatan seperti relativisasi, bukti alami, dan algebrizasi yang telah menghambat kemajuan, serta dugaan luas bahwa kelas-kelas tersebut berbeda.

Core questions

• Apakah menemukan solusi secara fundamental lebih sulit daripada memeriksanya?
• Mengapa jawabannya bergantung pada apakah ada satu masalah NP-lengkap dalam P?
• Bagaimana dunia akan terlihat jika P sama dengan NP, dan jika tidak?
• Mengapa puluhan tahun upaya gagal menyelesaikan pertanyaan ini?

Key theories

Kesetaraan dengan NP-completeness

P sama dengan NP jika dan hanya jika setiap masalah NP-lengkap memiliki algoritma waktu polinomial, sehingga pertanyaan luas ini mereduksi pada keterpecahan masalah konkret tunggal seperti satisfiability.

Hambatan bukti

Hasil relativisasi, bukti alami, dan algebrizasi menunjukkan bahwa teknik bukti utama yang diketahui tidak dapat menyelesaikan P versus NP, menjelaskan kesulitan dan memandu pencarian metode baru yang fundamental.

Clinical relevance

Ketidaksetaraan P dan NP yang diasumsikan adalah asumsi kerja di balik perlakuan masalah NP-hard sebagai tidak dapat dipecahkan dan di balik keamanan kriptografi, karena penyelesaian masalah NP yang efisien akan merusak enkripsi yang banyak digunakan; bukti konstruktif bahwa P sama dengan NP akan mengubah optimisasi, logistik, dan sains.

History

Cook merumuskan pertanyaan ini pada tahun 1971 bersamaan dengan NP-completeness, dan dengan cepat diakui sebagai fundamental. Upaya melalui batas bawah sirkuit pada tahun 1980-an menghadapi hambatan bukti alami yang diidentifikasi oleh Razborov dan Rudich, dan pada tahun 2000 Clay Mathematics Institute menamakannya masalah Millennium Prize dengan hadiah satu juta dolar.

Debates

Akankah P versus NP pernah terselesaikan, dan apa jawabannya?

Sebagian besar peneliti menduga bahwa P tidak sama dengan NP, tetapi tidak ada bukti yang ada dan teknik yang diketahui terbukti tidak memadai. Pendapat berbeda mengenai apakah penyelesaian sudah dekat, membutuhkan matematika yang radikal baru, atau apakah pertanyaan tersebut bahkan mungkin independen dari aksioma standar.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

Apa yang akan terjadi jika P sama dengan NP?

Banyak masalah yang sekarang diyakini tidak dapat dipecahkan, mulai dari penjadwalan optimal hingga memecahkan kode kriptografi, akan memiliki algoritma yang efisien, dan tindakan menemukan solusi tidak akan lebih sulit daripada memeriksanya. Dampaknya terhadap perdagangan, keamanan, dan sains akan sangat besar, yang merupakan bagian dari mengapa sebagian besar ahli memperkirakan P tidak sama dengan NP.

Mengapa masalah ini sangat sulit dipecahkan?

Membuktikan P sama dengan NP membutuhkan algoritma cepat untuk masalah NP-lengkap, yang belum ditemukan oleh siapa pun; membuktikan bahwa keduanya berbeda membutuhkan menunjukkan bahwa algoritma semacam itu tidak dapat ada. Hasil pada relativisasi dan bukti alami menunjukkan bahwa teknik standar secara inheren tidak mampu menetapkan yang terakhir, sehingga pendekatan yang benar-benar baru diperlukan.