Konsensus tentang P = NP di dunia di mana RP = NP

12

secara luas dikira salah.RP=NP

Tetapi bayangkan sejenak bahwa itu benar. Dalam kasus seperti itu, seberapa besar kemungkinan ?P=NP

Dengan kata lain: di dunia di mana , apa yang mungkin masih dilihat sebagai penghalang bagi kita untuk percaya P = N P ?RP=NPP=NP

cc.complexity-theory complexity-classes conditional-results Giorgio Camerani
sumber
3
Dengan kata lain, Anda meminta oracle relatif yang RP = NP tetapi P NP. ≠
Yuval Filmus
Iya. Saya ingin tahu apakah, di dunia di mana , kondisi tambahan yang perlu benar untuk P ≠ N P lebih ketat dan tidak mungkin dibandingkan dengan kondisi tambahan yang perlu benar untuk P = N P . RP=NPP≠NPP=NP
Giorgio Camerani
7
@Yuval Filmus: Saya tidak tahu apakah pertanyaannya adalah tentang penghalang relativisasi, tetapi jika ya, maka ada oracle relatif terhadap RP = EXP (yang menyiratkan P ≠ RP = NP). Saya tidak dapat menemukan referensi untuk fakta ini sekarang, tetapi dinyatakan dalam komentar setelah Teorema 6 di Heller 1986 dengan referensi ke dua makalah oleh Kurtz dan oleh Heller, keduanya dalam proses "Konferensi Teori Kompleksitas Komputasi" pada Maret 1983.
Tsuyoshi Ito

Jawaban:

14

Jujur saja, saya tidak berpikir bahwa Stack Exchange adalah tempat yang cocok untuk meminta prediksi di masa depan. Meskipun demikian, saya akan mengirim tanggapan karena itu menyenangkan untuk bermain dengan ide peramalan.

Sejauh yang saya tahu, kemungkinan P ≠ RP = NP belum dikesampingkan. Selain itu, ada bahasa A sehingga RP A = EXP A [Hel83, Kur83], yang segera menyiratkan bahwa P A ≠ RP A = NP A . (Saya belum memeriksa [Hel83] atau [Kur83], dan saya mengambil hasil dan referensi dari komentar setelah Teorema 6 di [Hel86].) Dengan kata lain, bahkan membuktikan implikasinya RP = NP ⇒ P = NP membutuhkan teknik nonrelativizing, dan oleh karena itu dapat dimengerti bahwa implikasi ini belum terbukti.

(Lance Fortnow telah membahas hasil serupa di blog Computational Complexity: Hasil Oracle Baik Untuk Anda .)

Sekarang mari kita beralih ke bagian meramal.

Seberapa banyak hasil ramalan ini menceritakan tentang kemungkinan P = NP di dunia di mana RP = NP telah terbukti? Tidak banyak. Paling tidak, itu tidak boleh dianggap sebagai bukti bahwa di dunia di mana RP = NP telah terbukti, masih mungkin sulit untuk membuktikan P = NP. Dalam dunia seperti itu, beberapa teknik baru nonrelativizing yang kuat diketahui manusia, dan oleh karena itu tidak masuk akal untuk menafsirkan "memerlukan teknik nonrelativizing" sebagai bukti kesulitan.

Berbicara lebih luas, jika RP = NP telah dibuktikan terlepas dari semua keyakinan (dan juga hambatan teknik bukti) yang menentangnya, maka pemahaman intuitif kita saat ini tentang perhitungan yang efisien kemungkinan akan sangat salah. Jelas kita tidak dapat menerapkan intuisi kita saat ini pada alasan tentang dunia di mana intuisi kita saat ini gagal secara spektakuler. Saya tidak berpikir bahwa kita dapat membuat tebakan yang berpendidikan tentang dunia seperti itu kecuali untuk apa yang telah dibuktikan dengan keras.

Referensi

[Hel83] Hans Heller. Pada hierarki polinomial yang direlatifikasi meluas ke dua tingkat. Dalam Prosiding Konferensi tentang Teori Kompleksitas Komputasi , hal. 109–114, UC Santa Barbara, Maret 1983.

[Hel86] Hans Heller. Pada kelas kompleksitas eksponensial dan probabilistik relativized. Informasi dan Kontrol , 71 (3): 231–243, Desember 1986. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] S. Kurtz (Stuart A. Kurtz?). Struktur halus NP: Relativizations. Dalam Prosiding Konferensi tentang Teori Kompleksitas Komputasi , hlm. 42-50, UC Santa Barbara, Maret 1983.

Tsuyoshi Ito
sumber
'Jelas kita tidak dapat menerapkan intuisi kita saat ini pada alasan tentang dunia di mana intuisi kita saat ini gagal secara spektakuler' .... ini adalah pernyataan besar.
T ....