Apakah sebuah oracle pernah berguna jika Anda tidak dapat mengontrol instance input?

Katakanlah adalah oracle untuk masalah di , tapi saya tidak bisa menyebut oracle ini dengan instance input apa pun. Sebagai gantinya, setiap kali saya menelepon saya akan mendapatkan contoh dan solusi acak. Jadi, saya tahu itu$F$$\mathbb{NP}$$F$$F$ sebenarnya mampu memecahkan sewenang-wenang $\mathbb{NP}$Masalah-sulit, saya tidak bisa menentukan yang mana saya ingin menyelesaikannya.

Apakah mungkin untuk menggunakan oracle seperti itu untuk menyelesaikan $\mathbb{NP}$Masalah -complete lebih cepat? Perasaan saya mengatakan tidak karena penggunaan naungan oracle masih membutuhkan$O(2^n)$waktu dengan menelepon oracle cukup untuk memeriksa setiap solusi. Saya hanya tidak bisa memikirkan cara untuk membuktikan ini.

Seperti yang ditunjukkan Xodarap, jika Anda memerlukan algoritme Anda dengan "oracle acak" untuk selalu menampilkan jawaban yang benar, maka oracle acak tidak berguna. Masalahnya menjadi lebih menarik jika kita membiarkan probabilitas kesalahan yang kecil (di mana probabilitas tersebut berkenaan dengan instance acak yang dipilih oleh oracle).

Selain itu, seperti yang ditunjukkan oleh Vor dalam komentar pada pertanyaan, tidak ada artinya untuk mengatakan "contoh acak" tanpa menentukan distribusi probabilitas. Salah satu asumsi yang masuk akal untuk dibuat di sini adalah bahwa instance acak ini dipilih secara seragam secara acak dari himpunan semua string panjang p ( n ), di mana n adalah panjang input dan p adalah beberapa polinomial tetap. Kita bisa membuat asumsi lain, lebih lemah, pada distribusi probabilitas.

Di sini kita akan membuat asumsi yang cukup umum, dan akan menunjukkan bahwa keberadaan algoritma waktu polinomial acak dengan "ramalan acak" untuk masalah lengkap NP memiliki konsekuensi yang mengejutkan bahkan di bawah asumsi yang lemah ini.

Mari kita jatuhkan persyaratan bahwa "oracle acak" akan menyelesaikan masalah dalam NP (pada contoh yang dipilih secara acak). Sekarang "oracle acak" dapat berupa distribusi probabilitas yang telah ditentukan sebelumnya atas string panjang polinomial, dan setiap kali ditanya, ia memancarkan string sesuai dengan distribusi probabilitas ini. Satu-satunya persyaratan adalah bahwa distribusi probabilitas ini hanya bergantung pada panjang input. Perhatikan bahwa model Anda memang merupakan kasus khusus dari model ini. Dalam model Anda, distribusi probabilitas diperlukan untuk memiliki bentuk berikut: pertama memilih sebuah seragam acak contoh y dari satu set tergantung pada panjang input, dan kemudian kembali sepasang ( y , g ( y )), di mana g: {0, 1} * → {0, 1} adalah fungsi karakteristik dari beberapa masalah keputusan dalam NP. Sekarang kita membiarkan setiap distribusi probabilitas, selama distribusi ditentukan oleh panjang masukan saja.

"Peramal" dari bentuk umum ini disebut saran acak . Kelas masalah keputusan yang dapat diputuskan oleh algoritma waktu polinomial acak dengan saran acak (dengan kesalahan dua sisi terikat) disebut BPP / rpoly, dan diketahui bahwa kelas ini sama dengan P / poli . (Penyertaan BPP / rpoly⊆P / poli dapat dibuktikan dengan cara yang sama seperti penyertaan terkenal BPP⊆P / poli. Untuk bukti yang terakhir, lihat misalnya Teorema 6.3 dari Goldreich [Gol08].)

Ini berarti bahwa jika masalah NP-complete dapat diselesaikan dalam model Anda, maka NP⊆P / poly. Namun, diketahui bahwa NP⊆P / poli menyiratkan bahwa hierarki polinomial runtuh ke tingkat kedua [KW98, Cai07]. Kebanyakan ahli teori kompleksitas menganggap keruntuhan hierarki polinomial sebagai kejutan besar. Jika kami percaya bahwa hierarki polinom tidak runtuh, maka masalah NP-complete tidak dapat diselesaikan secara efisien dengan "oracle acak" dalam pengertian Anda.

Referensi

[Cai07] Jin-Yi Cai. S ₂ ^p ⊆ ZPP ^NP . Jurnal Ilmu Komputer dan Sistem , 73 (1): 25–35, Februari 2007. DOI: 10.1016 / j.jcss.2003.07.015 .

[Gol08] Oded Goldreich. Kompleksitas Komputasi: Perspektif Konseptual . Cambridge University Press, 2008.

[KW98] Johannes Köbler dan Osamu Watanabe. Konsekuensi runtuhnya baru NP memiliki sirkuit kecil. Jurnal SIAM tentang Komputer , 28 (1): 311–324, 1998. DOI: 10.1137 / S0097539795296206 .

Mari kita secara khusus memikirkan masalah NP-complete favorit semua orang: 3SAT.

Mungkin saja (walaupun tidak mungkin) bahwa setiap kali Anda menelepon oracle Anda, itu memberi Anda tugas untuk contoh yang sama. Secara khusus, setiap kali itu bisa memberi Anda tugas untuk kalimat sepele:

Tapi Anda sudah tahu tugas untuk ini. Jadi Oracle Anda tidak bisa berguna.

Lebih formal lagi, jika kami menyebut oracle Anda $A$, kemudian $P^A\not=NP$ (asumsi $P\not=NP$...)