Bagaimana tidak menyelesaikan P = NP?

Ada banyak upaya untuk membuktikan atau , dan secara alami banyak orang berpikir tentang pertanyaan itu, memiliki ide untuk membuktikan arah mana pun.P ≠ N $\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Saya tahu bahwa ada pendekatan yang terbukti tidak berhasil, dan mungkin ada lebih banyak yang memiliki sejarah gagal. Tampaknya juga ada yang disebut penghalang yang banyak upaya bukti gagal atasi.

Kami ingin menghindari menyelidiki jalan buntu, jadi apa itu?

Saya akan mengatakan hambatan yang paling terkenal untuk memecahkan adalah$P=NP$

1. Relativization (seperti yang disebutkan oleh Ran G.)
2. Bukti Alam - berdasarkan asumsi kriptografi tertentu, Rudich dan Razborov membuktikan bahwa kami tidak dapat membuktikan menggunakan kelas bukti yang disebut bukti alami.$P\neq NP$
3. Algebrization - oleh Scott Aaronson dan Avi Wigderson. Mereka membuktikan bahwa bukti bahwa algebrize tidak dapat memisahkan danN $P$$NP$

Satu lagi yang saya kenal adalah hasil bahwa tidak ada formulasi LP yang dapat menyelesaikan TSP (Itu dibuktikan oleh Yannakakis untuk LP simetris dan baru-baru ini diperluas ke LP umum). Berikut adalah posting blog yang membahas hasilnya.

Catatan: Saya belum memeriksa jawabannya dengan hati-hati dan ada bagian yang hilang untuk ditulis, anggap itu konsep pertama.

Jawaban ini dimaksudkan terutama untuk orang-orang yang bukan peneliti dalam teori kompleksitas atau bidang terkait. Jika Anda adalah ahli teori kompleksitas dan telah membaca jawabannya, beri tahu kami jika Anda melihat ada masalah atau punya ide untuk meningkatkan jawabannya.

Di mana Anda dapat menemukan solusi P vs. NP yang diklaim

• Ada halaman P-versus-NP yang memiliki daftar klaim tersebut.
• Artikel-artikel yang mengklaim untuk menyelesaikan pertanyaan tersebut secara teratur diposting di arXiv .

Daftar lain tentang bagaimana tidak menyelesaikan P vs. NP

Lance Fortnow, Jadi Anda Mengira Anda Setuju P verus NP , 2009

Scott Aaronson, Delapan Tanda A Diklaim Bukti P Is NP Salah , 2010

Halaman Polymath untuk makalah Deolalikar , di mana bagian bacaan lebih lanjut memiliki daftar referensi yang bagus tentang masalah tersebut.

Bagaimana tidak mendekati P vs. NP

Biarkan saya membahas "bagaimana tidak mendekati P vs NP" bukan dalam arti ide yang tidak akan berhasil tetapi dalam arti yang lebih umum. P vs. NP adalah masalah yang mudah dinyatakan (lihat juga jawaban saya di sini ):

NP = P: Untuk setiap masalah keputusan dengan algoritma verifikasi waktu polinomial ada algoritma waktu polinomial.

atau setara

Ada algoritma waktu polinomial untuk SAT.
SAT dapat diganti dengan masalah NP-complete lainnya .

.

Seringkali orang terlalu menyederhanakan dan terlalu memfilsafkan masalah dan membesar-besarkan kepentingan praktis masalah (sebagaimana dinyatakan di atas). Pernyataan seperti itu sering dimaksudkan untuk memberikan intuisi, tetapi tidak dengan cara apa pun menggantikan pernyataan matematika sebenarnya dari masalah.

Efisiensi teoretis tidak sama dengan kelayakan dalam praktik.

Biarkan saya pertama-tama dengan konsekuensi praktis yang berlebihan.

I. Ada kemungkinan bahwa P = NP tetapi tidak membantu untuk masalah dalam praktek!

Katakan misalnya bahwa SAT dalam P tetapi algoritma tercepat untuk waktu berjalannya adalah . Algoritma ini tidak ada gunanya digunakan.$2^{2^{64}} n^{65536} + 2^{2^{128}}$

II Ada kemungkinan bahwa P NP dan kita dapat memecahkan masalah NP-complete secara efisien .$\neq$

Katakan misalnya bahwa SAT tidak dalam P tetapi memiliki algoritma dengan waktu berjalan .$n^{\lg^*\lg^* n}$

Untuk memberikan input yang akan menghasilkan Anda harus menggunakan lebih banyak elektron yang diperkirakan ada di alam semesta. Jadi eksponen pada dasarnya .$\lg^* n > 6$$2$

Poin utama di sini adalah bahwa P adalah model abstrak sederhana dari perhitungan yang efisien, kompleksitas kasus terburuk adalah model sederhana abstrak untuk memperkirakan biaya perhitungan, dll. Semua ini adalah abstraksi, tetapi tidak ada seorang pun dalam praktik yang akan mempertimbangkan algoritma seperti yang ada di (I) di atas sebagai algoritma yang efisien kok. P adalah model abstrak yang bagus, ia memiliki sifat-sifat yang bagus, membuat masalah teknis menjadi mudah, dan itu adalah yang bermanfaat. Namun seperti semua abstraksi matematis, ia menyembunyikan detail yang dalam praktiknya mungkin kita pedulikan. Ada berbagai model yang lebih halus tetapi model yang lebih rumit menjadi kurang bagus untuk diperdebatkan.

Apa yang orang peduli dalam praktek adalah untuk menghitung sebuah jawaban untuk masalah ini untuk kasus yang mereka pedulikan menggunakan akal jumlah sumber daya. Ada tugas yang tergantung dan harus dipertimbangkan.

Mencoba menemukan algoritma yang lebih baik untuk contoh praktis masalah NP-hard adalah upaya yang menarik dan layak. Ada algoritma heuristik SAT-solver yang digunakan dalam industri dan dapat memecahkan contoh praktis SAT dengan jutaan variabel. Bahkan ada Kompetisi SAT Internasional .

(Tetapi ada juga contoh konkret kecil yang gagal dan gagal semua algoritma ini, kita dapat benar-benar membuktikan bahwa semua pemecah SAT modern membutuhkan waktu yang eksponensial untuk menyelesaikan contoh sederhana seperti Prinsip Pigeonhole proposisional .)

Perlu diingat bahwa kebenaran dan waktu menjalankan program tidak dapat diperoleh hanya dari menjalankan program secara instan . Tidak masalah berapa kali Anda mencoba, tidak ada jumlah yang cukup. Ada banyak kemungkinan input yang tak terhingga dan Anda harus menunjukkan kebenaran dan efisiensi (yaitu waktu yang berjalan polinomial) dari program untuk semuanya. Singkatnya, Anda membutuhkan bukti matematis tentang kebenaran dan efisiensi. Jika Anda tidak tahu apa itu bukti matematika maka Anda harus terlebih dahulu mempelajari beberapa matematika dasar (baca buku teks matematika / kombinatorik / teori grafik, ini adalah topik yang bagus untuk belajar tentang apa yang dianggap sebagai bukti matematika).

Juga berhati-hatilah dengan klaim lain tentang P vs NP dan konsekuensi dari jawabannya. Klaim semacam itu seringkali didasarkan pada penyederhanaan yang serupa.

Ahli teori kompleksitas tidak terlalu peduli dengan jawaban untuk P vs. NP!

Saya sedikit melebih-lebihkan. Tentu saja kami peduli tentang jawaban untuk P vs NP. Tapi kami peduli dalam konteksnya. P vs NP adalah masalah utama kami tetapi itu bukan tujuan akhir. Ini adalah masalah yang mudah dinyatakan, melibatkan banyak ide mendasar, berguna untuk menjelaskan jenis pertanyaan yang kami minati kepada orang-orang yang tidak terbiasa dengan topik tersebut. Tapi kami tidak mencari sedikit jawaban Ya / Tidak untuk pertanyaan itu.

Kami mencari pemahaman yang lebih baik tentang sifat komputasi yang efisien . Kami percaya bahwa menyelesaikan pertanyaan akan datang dengan pemahaman seperti itu dan itulah alasan sebenarnya kami peduli. Ini adalah bagian dari badan penelitian besar. Jika Anda ingin merasakan apa yang kami lakukan, lihatlah pada buku teks teori kompleksitas yang baik, misalnya Arora dan Barak "The Complexity Theory: A Modern Approach " ( draft version ).

Mari kita asumsikan bahwa seseorang datang dengan bukti P NP terenkripsi sepenuhnya formal dan kami dapat memverifikasi kebenarannya ke tingkat kepercayaan yang sangat tinggi dengan memilih dan mendekripsi beberapa bit bukti (lihat Zero-Knowledge Proof dan PCP theorem ) . Jadi kita dapat memverifikasi klaim dengan probabilitas kesalahan kurang dari meteor yang mengenai rumah kita, kita cukup yakin buktinya benar dan P = NP, tetapi kita tidak tahu buktinya. Itu tidak akan menciptakan banyak kepuasan atau menggairahkan bagi kita. Bukti formal itu sendiri tidak akan terlalu memuaskan. Apa yang kita cari bukanlah bukti formal, yang kita cari adalah pengertian.$\neq$

Singkatnya, dari sudut pandang teori kompleksitas

P vs. NP bukan puzzle dengan jawaban Ya / Tidak. Kami mencari jawaban untuk P vs NP karena kami pikir itu akan datang pemahaman yang lebih baik tentang sifat komputasi yang efisien. Sebuah jawaban tanpa kemajuan besar dalam pemahaman kita tidak terlalu menarik.

Sudah terlalu banyak kesempatan bahwa non-pakar mengklaim solusi untuk P vs NP, dan klaim-klaim tersebut biasanya mengalami masalah yang tidak akan mereka buat jika mereka hanya membaca buku teks standar tentang teori kompleksitas.

Masalah umum P = NP

Klaim P = NP tampaknya lebih umum. Saya pikir yang berikut ini adalah tipe yang paling umum. Seseorang mempunyai ide dan menulis sebuah program dan mengujinya pada beberapa contoh dan berpikir ini adalah waktu polinomial dan dengan benar memecahkan masalah NP-complete. Seperti yang saya jelaskan di atas, tidak ada jumlah pengujian yang akan menunjukkan P = NP. P = NP membutuhkan bukti matematis , bukan hanya program yang tampaknya menyelesaikan masalah NP-lengkap dalam waktu polinomial.

Upaya ini biasanya mengalami salah satu dari dua masalah:

I. algoritma ini bukan waktu polinomial.

II algoritma tidak menyelesaikan semua instance dengan benar.

Tanda-tanda bahwa argumen P NP tidak benar$\neq$

[ditulis]

Cara memeriksa apakah algoritme Anda tidak benar - benar berfungsi

Anda tidak dapat menunjukkan bahwa algoritma Anda berfungsi dengan benar dengan menguji. Tetapi Anda dapat menunjukkan bahwa itu tidak berfungsi dengan benar dengan menguji! Jadi di sini adalah bagaimana Anda dapat memastikan bahwa algoritma Anda tidak benar jika Anda bersedia melakukan beberapa pekerjaan.

Pertama, tulis program untuk mengonversi instance SAT (dalam format CNF standar) ke masalah NP-hard yang Anda pecahkan. SAT adalah salah satu masalah NP-hard yang paling banyak dipelajari dan pengurangan dari masalah lain menjadi SAT biasanya mudah. Kedua, ambil contoh-contoh yang dibutuhkan oleh SAT-solver yang canggih (misalnya, ambil contoh dari kompetisi SAT) dan berikan mereka ke algoritma Anda dan lihat bagaimana kinerja algoritma Anda. Cobalah contoh-contoh sulit yang diketahui seperti Prinsip Pigeonhole proposisional (dan jangan menipu dengan mengkodekannya sebagai kasus khusus), contoh kriptografi (seperti Tantangan Anjak RSA ), contoh k-SAT acak dekat ambang , dll.

Demikian pula Anda dapat memeriksa bahwa algoritma Anda tidak efisien. Misal, jika Anda berpikir waktu berjalan algoritme Anda bukan tetapi butuh waktu berhari-hari untuk menyelesaikan contoh ukuran say 1000. Perbaiki batas waktu berjalan terburuk berdasarkan polinomial kasus yang menurut Anda dimiliki algoritma Anda. Ambil contoh dan perkirakan waktu yang dibutuhkan algoritma Anda untuk menyelesaikannya dan periksa apakah cocok dengan perkiraan Anda.$10 n^2$

Cara memeriksa algoritme P = NP ide Anda tidak dapat bekerja

Jika Anda melakukan ini, Anda akan cukup yakin bahwa algoritme Anda tidak berfungsi (jika bekerja lebih baik daripada yang canggih, SAT-solver kemudian berkompetisi dalam kompetisi berikutnya dan banyak orang akan tertarik mempelajari algoritme dan gagasan Anda).

Sekarang Anda tahu itu tidak benar-benar berfungsi tetapi itu tidak cukup. Kamu ingin tahu kenapa,

apakah alasan algoritme saya tidak berfungsi karena masalah kecil yang dapat diperbaiki atau apakah ada alasan mendasar mengapa tidak dapat berfungsi?

Kadang-kadang masalah dengan algoritma itu sederhana dan orang dapat mengidentifikasi apa yang salah secara konseptual. Hasil terbaik adalah Anda memahami alasan mengapa ide Anda tidak berhasil. Seringkali bukan itu masalahnya, ide Anda tidak berhasil tetapi Anda tidak dapat menemukan alasannya. Dalam hal ini perlu diingat:

memahami mengapa beberapa ide tidak bisa bekerja bisa lebih sulit daripada memecahkan P vs NP!

Jika Anda dapat memformalkan ide Anda cukup, Anda mungkin dapat membuktikan keterbatasan ide tertentu (misalnya ada hasil yang mengatakan formalisasi algoritma serakah tertentu tidak dapat menyelesaikan masalah NP-complete). Namun, ini bahkan lebih sulit, dan Anda tidak memiliki banyak peluang jika Anda belum membaca buku teks teori kompleksitas standar.

Kadang bahkan tidak ada ide konseptual yang jelas mengapa algoritma harus bekerja, yaitu didasarkan pada beberapa heuristik yang tidak dipahami dengan baik . Jika Anda tidak memiliki ide konseptual yang jelas tentang mengapa algoritma Anda harus bekerja maka Anda mungkin tidak memiliki banyak kesempatan dalam memahami mengapa itu tidak!

Masalah umum dengan klaim P NP$\neq$

Meskipun sebagian besar ahli berpikir P NP lebih mungkin daripada P = NP, klaim tersebut tampaknya kurang umum. Alasannya adalah membuktikan batas bawah tampaknya menjadi tugas yang lebih sulit daripada merancang algoritma (tetapi sering membuktikan batas bawah dan batas atas terkait secara intrinsik ).$\neq$

Edisi 1: penulis tidak tahu definisi P dan NP, atau lebih buruk lagi tidak mengerti apa itu bukti matematika. Karena penulis tidak memiliki pelatihan matematika dasar, ia tidak mengerti ketika ia diberi tahu apa yang ia presentasikan bukanlah bukti (mis. Langkah-langkahnya tidak mengikuti dari yang sebelumnya).

Edisi 2: penulis bingung "kita tidak tahu bagaimana" dengan "ketidakmungkinan matematis". Misalnya mereka membuat berbagai asumsi yang tidak bisa dibenarkan dan ketika ditanya "mengapa pernyataan ini benar?" mereka menjawab "bagaimana mungkin itu salah?". Salah satu yang umum adalah mengasumsikan bahwa setiap program yang memecahkan masalah harus melalui langkah-langkah tertentu, misalnya ia harus menghitung nilai-nilai perantara tertentu, karena ia tidak dapat memikirkan cara alternatif untuk menyelesaikan masalah.

[untuk diselesaikan]

Tanda-tanda bahwa argumen P NP tidak benar$\neq$

[ditulis]

Cara memeriksa ide P NP Anda tidak dapat bekerja$\neq$

Jika suatu klaim tidak mengalami masalah mendasar ini maka menolaknya menjadi lebih sulit. Pada level pertama seseorang dapat menemukan langkah yang salah dalam argumen. Tanggapan khas dari penulis adalah bahwa saya dapat memperbaikinya dan ini bolak-balik dapat berlangsung. Mirip dengan P = NP solusi, seringkali sangat sulit untuk menemukan masalah mendasar dengan sebuah ide yang dapat menunjukkan bahwa ia tidak dapat bekerja, terutama ketika ide itu sendiri bersifat informal.

Dalam kasus terbaik, jika kita dapat memformalkan ide dan mengidentifikasi hambatan yang menunjukkan ide tidak dapat bekerja, kita telah membuktikan hasil penghalang baru (ini adalah bagaimana upaya untuk membuktikan P NP menggunakan sirkuit batas bawah mengarah ke penghalang Bukti Alam ).$\neq$

Mungkin teknik yang paling umum yang tidak dapat digunakan adalah relativization , yaitu, memiliki TM dengan akses oracle.

Ketidakmungkinan berikut dari sebuah makalah oleh Theodore Baker, John Gill, Robert Solovay yang menunjukkan keberadaan dua nubuat (bahasa), dan sedemikian rupa sehingga dan .B P A = NP A P B ≠ NP $A$$B$$\text{P}^A = \text{NP}^A$$\text{P}^B \ne \text{NP}^B$

Jadi, jika beberapa bukti untuk, katakanlah, dapat direlatifikasi, ini berarti bahwa untuk semua nubuat , yang bertentangan dengan keberadaan .O P O ≠ NP O$\text{P}\ne \text{NP}$$O$$\text{P}^O \ne \text{NP}^O$$A$

Secara khusus, ini berarti diagonalisasi tidak dapat digunakan untuk membuktikan karena bukti-bukti tersebut dapat direlatifikasi, lihat misalnya catatan kuliah ini .$\text{P} \stackrel{?}{=} \text{NP}$

Saya sarankan membaca posting blog ini oleh Lance Fortnow :

1. So You Think You Settled P verus NP Anda salah. Cari tahu. Kadang-kadang Anda masih bisa menyelamatkan sesuatu yang menarik dari bukti cacat Anda.
2. Anda yakin buktinya benar. Keyakinan Anda salah. Kembali ke langkah 1.
3. Apakah Anda membuat asumsi atau jalan pintas, bahkan yang kecil dan jelas? Apakah Anda menggunakan kata-kata seperti "jelas", "jelas", "mudah dilihat", "harus", "harus" atau "mungkin"? Anda mengklaim untuk menyelesaikan mungkin pertanyaan paling penting dalam semua matematika. Anda tidak bisa membuat asumsi. Kembali ke langkah 1.
4. Apakah Anda benar-benar memahami masalah P versus NP? Untuk memperlihatkan P ≠ NP, Anda perlu menemukan bahasa L di NP sedemikian rupa sehingga untuk setiap k dan setiap mesin M yang berjalan dalam waktu (n = panjang input), M gagal menghitung dengan benar L. L adalah serangkaian string. Tidak ada lagi. L tidak dapat bergantung pada M atau k. M dapat berupa program apa pun yang memproses string bit. M dapat bertindak sangat berbeda dari yang diharapkan dari cara Anda mendefinisikan L. Kembali ke langkah 1.$n^k$
5. Anda mengirimkan kertas Anda ke arsip online. Mungkin beberapa orang memberi tahu Anda apa yang hilang atau salah di koran Anda. Ini seharusnya menyebabkan Anda pergi ke langkah 1. Tetapi alih-alih Anda membuat beberapa perubahan yang tidak berarti pada makalah dan posting ulang Anda.
6. Akhirnya orang mengabaikan kertas Anda. Anda bertanya-tanya mengapa Anda tidak mendapatkan ketenaran dan kekayaan.
7. Anda mengirimkan makalah Anda ke jurnal.
8. Makalah itu ditolak. Jika Anda pintar, Anda akan kembali ke langkah 1. Tetapi jika Anda pintar, Anda tidak akan pernah sampai ke langkah 7.
9. Anda mengeluh kepada editor bahwa editor tidak mengerti buktinya atau mudah diperbaiki. Anda terkejut editor atau jurnal yang terhormat akan memperlakukan makalah Anda dengan cara ini.
10. Anda mengirim ulang makalah, naik banding, coba jurnal lain semua tetapi tidak berhasil.
11. Anda yakin "perusahaan" dengan sengaja menekan kertas Anda karena bidang kami akan menjadi jauh kurang menarik jika kami menyelesaikan masalah P versus NP sehingga kami harus tetap membuka dengan segala cara.
12. Jika saya katakan sebaliknya, apakah Anda akan mempercayai saya?

di sini adalah sudut / referensi / twist yang agak kabur / dalam / sulit / orang dalam yang berkaitan dengan pendekatan melalui sirkuit yang berasal dari tahun 1980 awalnya ditunjukkan kepada saya bertahun-tahun yang lalu oleh Luca Trevisan di tempat lain di dunia maya, dan juga ditegaskan kembali oleh Stasys Jukna, penulis yang sangat baik referensi dekat dengan subjek, Kompleksitas Fungsi Boolean: Kemajuan dan Batas (Algoritma dan Kombinatorik, Vol. 27 ).

orang dapat melihat tren sebelumnya dalam beberapa pemikiran Razborov yang akhirnya mengarah ke kertas Natural Proofs (disebut "naturalisasi"). ref [273] sangat teknis & sulit dan sepertinya tidak dikutip, dibangun di atas / diperluas, atau banyak diulang oleh makalah / buku selanjutnya meskipun Bukti Alami dapat dilihat sebagai generalisasi besar kemudian. kutipannya adalah dari John E Savages, ref Model of Computation yang sangat baik hal

Setelah menunjukkan bahwa kompleksitas sirkuit monoton dapat mengarah pada batas bawah eksponensial [270], Razborov [271] kemudian meragukan kemungkinan bahwa pendekatan ini akan mengarah pada batas ukuran sirkuit non-monoton eksponensial dengan membuktikan bahwa masalah pencocokan pada grafik bipartit, suatu masalah dalam P, memiliki ukuran sirkuit monoton super polinomial. Tardos [324] memperkuat batas bawah Razborov, menurunkan yang eksponensial. Kemudian Razborov [273] menunjukkan bahwa generalisasi yang jelas dari metode aproksimasi tidak dapat menghasilkan batas yang lebih baik daripada untuk fungsi Boolean pada input yang direalisasikan oleh sirkuit pada basis lengkap.$\Omega(n^2)$$n$

[270] AA Razborov, "Batas Bawah pada Kompleksitas Monoton dari Beberapa Fungsi Boolean," Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801, (dalam bahasa Rusia); Terjemahan bahasa Inggris di Soviet Math. Dokl. 31 (1985), 354–357

[271] AA Razborov, "Batas Bawah pada Kompleksitas Jaringan Monoton Permanen Logis," Mat. Zametki 37 (1985), 887–900, (dalam bahasa Rusia); Terjemahan bahasa Inggris dalam Matematika. Catatan 37 (6) (1985), 485–493.

[273] AA Razborov, "Tentang Metode Perkiraan," Proc. 21 Ann. ACM Symp. Theory of Computing (1989), 167–176.