Alasan untuk meyakini (atau tidak)

Tampaknya banyak orang percaya bahwa , sebagian karena mereka percaya bahwa anjak piutang tidak dapat dipecahkan. (Shiva Kintali telah mendaftarkan beberapa masalah kandidat lainnya di sini ). $P \ne NP \cap coNP$

Di sisi lain, Grötschel, Lovász, dan Schrijver telah menulis bahwa "banyak orang percaya bahwa ." Kutipan ini dapat ditemukan di Algoritma Geometrik dan Optimalisasi Kombinatorial, dan Schrijver membuat pernyataan serupa di Optimalisasi Kombinatorial: Polihedra dan Efisiensi . Gambar ini menjelaskan di mana Jack Edmonds berdiri tentang masalah ini. $P=NP\cap coNP$

Bukti apa yang mendukung keyakinan pada ? Atau untuk mendukung ? $P\ne NP\cap coNP$ $P=NP\cap coNP$

cc.complexity-theory np conditional-results Austin Buchanan
sumber

Tentukan "alasan." Benar-benar tidak ada bukti. Ini bukan sesuatu yang dapat diuji secara eksperimental. Sampai kita memiliki bukti satu atau lain cara, satu-satunya "alasan untuk percaya" itu adalah perasaan, baik bahwa beberapa masalah di

N P \cap c o N P

$NP \cap coNP$ bukanlah polinomial, atau naluri usus bahwa semuanya.

jmite

Saya berharap jawaban seperti apa yang diberikan Scott Aaronson untuk P versus NP .

Austin Buchanan

banyak ide yang sama berlaku. tidak setuju dengan jmite. ada banyak bukti tidak langsung, termasuk bukti eksperimental, beberapa seperti yang tercantum oleh aaronson.

vzn

Teorema 3.1 Permutasi Satu Arah dan Bahasa yang Menyaksikan Sendiri C. Homan dan M. Thakur, Jurnal Ilmu Komputer dan Sistem, 67 (3): 608-622, November 2003. [ as .pdf ] menyatakan bahwa P ≠ UP∩ coUP jika dan hanya jika ("kasus terburuk") permutasi satu arah ada. Teorema 3.2 mengingatkan 10 hipotesis lebih lanjut yang telah terbukti setara dengan P ≠ UP∩coUP.

Thomas Klimpel

Saya pikir anjak ∈ P banyak, banyak urutan besarnya lebih mungkin daripada P = NP ∩ coNP, jadi tentu saja bukan alasan bahwa saya percaya P = NP ∩ coNP.

Peter Shor

Jawaban:

Teorema 3.1 Permutasi Satu Arah dan Bahasa yang Menyaksikan Sendiri C. Homan dan M. Thakur, Jurnal Ilmu Komputer dan Sistem, 67 (3): 608-622, November 2003. [ as .pdf ] menyatakan bahwa jika dan hanya jika permutasi satu arah ("kasus terburuk") ada. Teorema 3.2 kenang 10 hipotesis lanjut yang telah terbukti setara dengan . $P≠UP∩coUP$ $P≠UP∩coUP$

Juga, kita memiliki alasan yang kuat untuk dugaan bahwa . Oleh karena itu, di atas teorema dan hasil dugaan dalam alasan kuat untuk percaya bahwa . $UP \ne NP$ $P \ne NP ∩ coNP$

Penafian: Saya memindahkan hasil edit Mohammad Al-Turkistany dari jawaban saya ke jawaban wiki komunitas ini. Dia percaya bahwa itu menjawab pertanyaan dengan sempurna karena keberadaan permutasi satu arah diyakini secara luas. Saya sendiri belum cukup memahami perbedaan antara fungsi satu arah "kasus terburuk" dan "kasus rata-rata" untuk mengklaim bahwa itu benar-benar menjawab pertanyaan.

Thomas Klimpel
sumber

Saya percaya bahwa ada generator nomor acak berkualitas tinggi yang sangat efisien ruang. Terlepas dari kepercayaan ini, saya biasanya menggunakan twister Mersenne dalam kode saya, yang berkualitas tinggi, tetapi tidak terlalu efisien ruang. Ada tautan yang hilang antara efisiensi ruang dan NP∩coNP, itu hanya perasaan bahwa ada tautan.

Biarkan saya mencoba memberikan satu alasan mengapa saya percaya bahwa "keacakan benar" dapat disimulasikan / diperkirakan sangat efisien ruang. Kita tahu bahwa dimungkinkan untuk menghasilkan angka pseudo-acak yang cukup acak untuk semua tujuan praktis (termasuk kriptografi). Kita juga tahu bahwa menggunakan (dalam jumlah kecil tetap) bilangan prima besar dalam konstruksi generator bilangan pseudo-acak jarang merupakan ide yang buruk. Kita tahu dari dugaan seperti Riemann bahwa hampir semua bilangan prima mengandung tingkat keacakan yang tinggi, tetapi kita juga tahu bahwa kita belum dapat membuktikan ini dengan seksama.

Apakah ada penjelasan intuitif mengapa bilangan prima berperilaku seperti bilangan acak? Bilangan prima adalah pelengkap bilangan komposit. Komplemen dari perangkat yang berperilaku baik seringkali lebih rumit daripada perangkat asli. Bilangan komposit terdiri dari bilangan prima, yang pada gilirannya telah memberikan set ini kompleksitas tertentu.

Latar Belakang Saya pernah mencoba memahami mengapa P ≠ NP sulit. Saya bertanya-tanya apakah kira-kira kelompok simetri dalam dari sebuah instance masalah oleh kelompok nilpotent mungkin tidak mengarah pada suatu "algoritma abstraksi" yang dapat melihat ke dalam struktur bagian dalam instance masalah. Tetapi kemudian saya menyadari bahwa bahkan menghitung struktur kelompok nilpotent mengandung anjak sebagai kasus khusus. Pertanyaan tentang subkelompok sederhana dari kelompok siklik dari urutan n setara dengan menentukan faktor utama dari n. Dan klasifikasi kelompok nilpoten terbatasmengandung subproblem yang lebih buruk terkait dengan isomorfisme grafik. Itu cukup untuk meyakinkan saya bahwa pendekatan ini tidak akan membantu. Tetapi langkah saya berikutnya adalah mencoba memahami mengapa anjak sulit, dan jawaban di atas adalah apa yang saya dapatkan. Itu sudah cukup untuk meyakinkan saya, jadi mungkin itu juga akan meyakinkan untuk orang lain. (Saya tidak tahu tentang groupoids atau semi-grup terbalik saat itu, yang mungkin lebih cocok daripada kelompok nilpotent untuk menangani simetri batin. Namun, argumen mengapa pendekatan seperti itu tidak akan efisien tetap sama.)

Thomas Klimpel
sumber

Saya tidak yakin bagaimana jawaban ini berhubungan dengan pertanyaan. Bisakah Anda menguraikan?

Matthias

@Matthias Jawabannya adalah alasan mengapa saya percaya bahwa P ≠ NP∩coNP. Jadi masalahnya mungkin bukan hubungannya dengan pertanyaan, tetapi bagaimana menjelaskan alasannya. Ada bentuk platonisme matematika yang terlibat, yang mengasumsikan bahwa struktur matematika mampu memodelkan atau mendekati hampir semua yang dapat ada di dunia ini. Keacakan sebenarnya adalah bagian dari apa yang bisa ada, dan jawabannya mencoba menjelaskan mengapa ada firasat bahwa keacakan ini sudah ada dalam konteks terbatas ruang yang cukup untuk menyebabkan P ≠ NP∩coNP. (Maaf, mungkin saya akan memperbaiki / menghapus komentar ini nanti.)

Thomas Klimpel

\neq

$\neq$

\cap

$\cap$

@Matthias saya menulis "... tautan yang hilang antara efisiensi ruang dan NP∩coNP, itu hanya firasat ..." dalam jawabannya. Saya bisa mencoba menjelaskan, tetapi saya khawatir ini tidak akan diterima dengan baik. Sebenarnya, saya kira Anda lebih suka referensi independen yang menunjuk ke arah itu daripada penjelasan saya sendiri. Di Kompleksitas Kebun Binatang , saya menemukan hasil yang dikutip "permutasi satu arah" kasus terburuk "ada jika dan hanya jika P tidak sama dengan UP ∩ coUP [ HT03 ]. Makalah ini online, tetapi saya belum membacanya ...

Thomas Klimpel