Apa itu "P = NP?", Dan mengapa itu merupakan pertanyaan yang begitu terkenal? [Tutup]

Pertanyaan apakah P = NP mungkin yang paling terkenal di semua Ilmu Komputer. Apa artinya? Dan mengapa ini sangat menarik?

Oh, dan untuk kredit tambahan, silakan kirim bukti kebenaran atau kepalsuan pernyataan itu. :)

P adalah singkatan dari polinomial time. NP adalah waktu polinomial non-deterministik.

Definisi:

• Waktu polinomial berarti bahwa kompleksitas algoritma adalah O (n ^ k), di mana n adalah ukuran data Anda (mis. Jumlah elemen dalam daftar yang akan diurutkan), dan k adalah konstanta.

• Kompleksitas adalah waktu yang diukur dalam jumlah operasi yang akan diambil, sebagai fungsi dari jumlah item data.

• Operasi adalah apa pun yang masuk akal sebagai operasi dasar untuk tugas tertentu. Untuk penyortiran, operasi dasar adalah perbandingan. Untuk perkalian matriks, operasi dasarnya adalah perkalian dua angka.

Sekarang pertanyaannya adalah, apa arti deterministik vs non-deterministik? Ada model komputasi abstrak, komputer imajiner yang disebut mesin Turing (TM). Mesin ini memiliki sejumlah negara terbatas, dan pita tak terbatas, yang memiliki sel-sel terpisah yang menjadi tempat seperangkat simbol terbatas dapat ditulis dan dibaca. Pada waktu tertentu, TM berada di salah satu kondisinya, dan sedang melihat sel tertentu pada rekaman itu. Bergantung pada apa yang dibacanya dari sel itu, ia dapat menulis simbol baru ke dalam sel itu, memindahkan selotip itu ke depan atau ke belakang, dan menuju ke keadaan yang berbeda. Ini disebut transisi negara. Cukup mengherankan, dengan secara hati-hati membangun negara dan transisi, Anda dapat merancang TM, yang setara dengan program komputer apa pun yang dapat ditulis.

Ada dua jenis TM yang menjadi perhatian kita di sini: deterministik dan non-deterministik. TM deterministik hanya memiliki satu transisi dari masing-masing negara untuk setiap simbol yang dibacanya dari rekaman itu. TM non-deterministik mungkin memiliki beberapa transisi seperti itu, yaitu ia dapat memeriksa beberapa kemungkinan secara bersamaan. Ini semacam seperti menelurkan banyak utas. Perbedaannya adalah bahwa TM non-deterministik dapat memunculkan sebanyak "utas" seperti yang diinginkan, sementara pada komputer nyata hanya sejumlah utas yang dapat dieksekusi pada suatu waktu (sama dengan jumlah CPU). Pada kenyataannya, komputer pada dasarnya adalah TM yang deterministik dengan kaset terbatas. Di sisi lain, TM non-deterministik tidak dapat direalisasikan secara fisik, kecuali mungkin dengan komputer kuantum.

Telah terbukti bahwa masalah apa pun yang dapat dipecahkan oleh TM non-deterministik dapat diselesaikan oleh TM deterministik. Namun, tidak jelas berapa lama waktu yang dibutuhkan. Pernyataan P = NP berarti bahwa jika suatu masalah membutuhkan waktu polinomial pada TM non-deterministik, maka seseorang dapat membangun TM deterministik yang akan menyelesaikan masalah yang sama juga dalam waktu polinomial. Sejauh ini tidak ada yang bisa menunjukkan bahwa itu bisa dilakukan, tetapi tidak ada yang bisa membuktikan bahwa itu juga tidak bisa dilakukan.

Masalah NP-complete berarti masalah NP X, sehingga setiap masalah NP Y dapat dikurangi menjadi X oleh reduksi polinomial. Itu menyiratkan bahwa jika ada orang yang datang dengan solusi waktu polinomial untuk masalah NP-lengkap, itu juga akan memberikan solusi waktu polinomial untuk setiap masalah NP. Dengan demikian itu akan membuktikan bahwa P = NP. Sebaliknya, jika ada yang membuktikan bahwa P! = NP, maka kami akan yakin bahwa tidak ada cara untuk memecahkan masalah NP dalam waktu polinomial pada komputer konvensional.

Contoh masalah NP-complete adalah masalah menemukan penugasan kebenaran yang akan membuat ekspresi boolean yang mengandung n variabel menjadi benar.
Untuk saat ini dalam praktiknya, masalah apa pun yang memerlukan waktu polinomial pada TM non-deterministik hanya dapat dilakukan dalam waktu eksponensial pada TM deterministik atau pada komputer konvensional.
Sebagai contoh, satu-satunya cara untuk menyelesaikan masalah penugasan kebenaran adalah dengan mencoba dua kemungkinan.

1. Masalah ya-atau-tidak ada dalam P ( P olynomial time) jika jawabannya dapat dihitung dalam waktu polinomial.
2. Sebuah ya atau tidak ada masalah dalam NP ( N on-deterministik P waktu olynomial) jika jawaban ya dapat diverifikasi dalam waktu polinomial.

Secara intuitif, kita dapat melihat bahwa jika masalah ada di P , maka itu adalah NP . Mengingat kemungkinan jawaban untuk masalah di P , kami dapat memverifikasi jawabannya hanya dengan menghitung ulang jawabannya.

Kurang jelas, dan jauh lebih sulit untuk jawabannya, adalah apakah semua masalah di NP berada di P . Apakah fakta bahwa kita dapat memverifikasi jawaban dalam waktu polinomial berarti bahwa kita dapat menghitung jawaban itu dalam waktu polinomial?

Ada sejumlah besar masalah penting yang diketahui sebagai NP- lengkap (pada dasarnya, jika ada masalah ini terbukti dalam P , maka semua masalah NP terbukti berada di P ). Jika P = NP , maka semua masalah ini akan terbukti memiliki solusi (waktu polinomial) yang efisien.

Sebagian besar ilmuwan percaya bahwa P ! = NP . Namun, belum ada bukti yang ditetapkan untuk P = NP atau P ! = NP . Jika ada yang memberikan bukti untuk dugaan tersebut, mereka akan memenangkan US $ 1 juta .

Untuk memberikan jawaban yang paling sederhana, saya bisa memikirkan:

Misalkan kita memiliki masalah yang membutuhkan sejumlah input, dan memiliki berbagai solusi potensial, yang mungkin atau mungkin tidak menyelesaikan masalah untuk input yang diberikan. Teka-teki logika dalam majalah puzzle akan menjadi contoh yang bagus: inputnya adalah kondisinya ("George tidak tinggal di rumah biru atau hijau"), dan solusi potensial adalah daftar pernyataan ("George hidup dalam warna kuning rumah, menanam kacang polong, dan memiliki anjing "). Contoh yang terkenal adalah masalah Travelling Salesman: diberikan daftar kota, dan waktu untuk berpindah dari kota mana saja ke kota lain, dan batas waktu, solusi potensial adalah daftar kota sesuai urutan penjual yang mengunjungi mereka, dan itu akan bekerja jika jumlah waktu perjalanan kurang dari batas waktu.

Masalah seperti itu ada di NP jika kita dapat secara efisien memeriksa solusi potensial untuk melihat apakah itu berfungsi. Misalnya, mengingat daftar kota yang harus dikunjungi oleh penjual, kami dapat menambahkan waktu untuk setiap perjalanan antar kota, dan dengan mudah melihat apakah itu di bawah batas waktu. Masalah ada di P jika kita dapat menemukan solusi secara efisien jika ada.

(Efisien, di sini, memiliki makna matematika yang tepat. Secara praktis, itu berarti bahwa masalah besar tidak terlalu sulit untuk dipecahkan. Ketika mencari solusi yang mungkin, cara yang tidak efisien adalah dengan mendaftar semua kemungkinan solusi potensial, atau sesuatu yang dekat dengan itu. , sementara cara yang efisien akan membutuhkan pencarian yang lebih terbatas.)

Oleh karena itu, masalah P = NP dapat diekspresikan dengan cara ini: Jika Anda dapat memverifikasi solusi untuk masalah yang dijelaskan di atas secara efisien, dapatkah Anda menemukan solusi (atau membuktikan tidak ada) secara efisien? Jawaban yang jelas adalah "Mengapa Anda harus bisa?", Dan itulah yang menjadi masalah saat ini. Tidak ada yang bisa membuktikannya dengan satu atau lain cara, dan itu mengganggu banyak ahli matematika dan ilmuwan komputer. Itu sebabnya siapa pun yang dapat membuktikan solusinya adalah untuk satu juta dolar dari Claypool Foundation.

Kami umumnya berasumsi bahwa P tidak sama dengan NP, bahwa tidak ada cara umum untuk menemukan solusi. Jika ternyata P = NP, banyak hal akan berubah. Sebagai contoh, kriptografi akan menjadi tidak mungkin, dan dengan itu segala jenis privasi atau verifikasi di Internet. Bagaimanapun, kita dapat secara efisien mengambil teks terenkripsi dan kunci dan menghasilkan teks asli, jadi jika P = NP kita dapat menemukan kunci secara efisien tanpa mengetahuinya sebelumnya. Password cracking akan menjadi sepele. Di sisi lain, ada seluruh kelas masalah perencanaan dan masalah alokasi sumber daya yang bisa kita selesaikan secara efektif.

Anda mungkin pernah mendengar deskripsi NP-complete. Masalah NP-complete adalah salah satu yang NP (tentu saja), dan memiliki properti yang menarik ini: jika ada di P, setiap masalah NP adalah, dan P = NP. Jika Anda dapat menemukan cara untuk secara efisien menyelesaikan masalah Travelling Salesman, atau teka-teki logika dari majalah puzzle, Anda dapat secara efisien menyelesaikan apa pun di NP. Masalah NP-lengkap, sedikit banyak, merupakan jenis masalah NP yang paling sulit.

Jadi, jika Anda dapat menemukan teknik solusi umum yang efisien untuk setiap masalah NP-complete, atau membuktikan bahwa tidak ada yang seperti itu, ketenaran dan kekayaan adalah milik Anda.

Ringkasan singkat dari pengetahuan saya yang sederhana:

Ada beberapa masalah komputasi yang mudah (seperti menemukan jalur terpendek antara dua titik dalam grafik), yang dapat dihitung cukup cepat (O (n ^ k), di mana n adalah ukuran input dan k adalah konstanta (dalam kasus grafik, ini adalah jumlah simpul atau tepi)).

Masalah lain, seperti menemukan jalur yang melintasi setiap simpul dalam grafik atau mendapatkan kunci pribadi RSA dari kunci publik lebih sulit (O (e ^ n)).

Tetapi CS berbicara bahwa masalahnya adalah bahwa kita tidak dapat 'mengubah' mesin Turing non-deterministik menjadi mesin deterministik, namun, kita dapat mengubah otomit terbatas non-deterministik (seperti parser regex) menjadi yang deterministik (well, Anda bisa, tetapi waktu proses mesin akan lama). Artinya, kita harus mencoba setiap jalur yang mungkin (biasanya profesor CS pintar dapat mengecualikan beberapa jalur).

Sangat menarik karena tidak ada yang tahu solusinya. Ada yang bilang itu benar, ada yang bilang itu salah, tapi tidak ada konsensus. Hal lain yang menarik adalah bahwa solusi akan berbahaya bagi enkripsi kunci publik / swasta (seperti RSA). Anda dapat memecahkannya semudah membuat kunci RSA sekarang.

Dan itu adalah masalah yang cukup menginspirasi.

Tidak banyak yang bisa saya tambahkan ke bagian P =? NP apa dan mengapa, tetapi dalam hal buktinya. Bukti tidak hanya akan bernilai kredit ekstra, tetapi juga akan menyelesaikan salah satu Masalah Milenium . Sebuah jajak pendapat yang menarik baru-baru ini dilakukan dan hasil yang dipublikasikan (PDF) pasti layak dibaca sehubungan dengan subjek bukti.

Pertama, beberapa definisi:

• Masalah khusus ada di P jika Anda dapat menghitung solusi dalam waktu kurang dari n^kbeberapa k, di mana nukuran input. Misalnya, penyortiran dapat dilakukan di n log nmana kurang dari n^2, jadi penyortiran adalah waktu polinomial.

• Masalahnya adalah di NP jika ada ksedemikian sehingga ada solusi ukuran paling banyak n^kyang dapat Anda verifikasi paling banyak dalam waktu n^k. Ambil 3-pewarnaan grafik: diberi grafik, 3-pewarnaan adalah daftar pasangan (simpul, warna) yang memiliki ukuran O(n)dan Anda dapat memverifikasi dalam waktu O(m)(atau O(n^2)) apakah semua tetangga memiliki warna yang berbeda. Jadi grafik hanya 3-warna jika ada solusi pendek dan mudah diverifikasi.

Definisi NP yang ekivalen adalah "masalah yang dipecahkan oleh mesin Turing N ondeterministic dalam waktu P olynomial". Meskipun itu memberi tahu Anda dari mana nama itu berasal, itu tidak memberi Anda perasaan intuitif yang sama seperti apa masalah NP.

Perhatikan bahwa P adalah subset dari NP: jika Anda dapat menemukan solusi dalam waktu polinomial, ada solusi yang dapat diverifikasi dalam waktu polinomial - cukup periksa bahwa solusi yang diberikan sama dengan yang Anda dapat temukan.

Mengapa pertanyaannya P =? NPmenarik? Untuk menjawab itu, pertama-tama perlu melihat apa masalah NP-complete. Sederhananya,

• Masalah L adalah NP-lengkap jika (1) L ada di P, dan (2) algoritma yang memecahkan L dapat digunakan untuk menyelesaikan masalah L 'di NP; yaitu, dengan memberikan instance L 'Anda dapat membuat instance L yang memiliki solusi jika dan hanya jika instance L' memiliki solusi. Secara formal, setiap masalah L 'di NP dapat direduksi menjadi L.

Perhatikan bahwa turunan L harus dihitung waktu polinomial dan memiliki ukuran polinomial, dalam ukuran L '; dengan cara itu, menyelesaikan masalah NP-lengkap dalam waktu polinomial memberi kita solusi waktu polinomial untuk semua masalah NP.

Berikut ini sebuah contoh: misalkan kita tahu bahwa 3-pewarnaan grafik adalah masalah NP-hard. Kami ingin membuktikan bahwa memutuskan kepuasan formula boolean juga merupakan masalah yang sulit.

Untuk setiap titik v, memiliki dua variabel boolean v_h dan v_l, dan persyaratan (v_h atau v_l): setiap pasangan hanya dapat memiliki nilai {01, 10, 11}, yang dapat kita anggap sebagai warna 1, 2 dan 3.

Untuk setiap sisi (u, v), memiliki persyaratan bahwa (u_h, u_l)! = (V_h, v_l). Itu adalah,

not ((u_h and not u_l) and (v_h and not v_l) or ...) menyebutkan semua konfigurasi dan ketentuan yang sama yang tidak ada di antara keduanya.

ANDBersama-sama semua kendala ini memberikan rumus boolean yang memiliki ukuran polinomial ( O(n+m)). Anda dapat memeriksa apakah butuh waktu polinomial untuk menghitung juga: Anda melakukan O(1)hal-hal langsung per vertex dan per edge.

Jika Anda bisa menyelesaikan rumus boolean yang saya buat, maka Anda juga bisa menyelesaikan pewarnaan grafik: untuk setiap pasangan variabel v_h dan v_l, biarkan warna v menjadi yang cocok dengan nilai-nilai variabel tersebut. Dengan membangun formula, tetangga tidak akan memiliki warna yang sama.

Oleh karena itu, jika 3-pewarnaan grafik adalah NP-complete, demikian juga boolean-formula-satisfiability.

Kita tahu bahwa 3-pewarnaan grafik adalah NP-complete; Namun, secara historis kita telah mengetahui bahwa dengan pertama-tama menunjukkan NP-kelengkapan boolean-circuit-satisfiability, dan kemudian menguranginya menjadi 3-colorability (bukan sebaliknya).