Sangat mudah untuk melihat bahwa jika maka ada masalah pencarian total yang tidak dapat diselesaikan dalam waktu polinomial (buat masalah pencarian total dengan memiliki saksi untuk keanggotaan dan saksi bukan anggota).
Apakah yang sebaliknya juga benar, yaitu
Apakah keberadaan total masalah pencarian tidak dapat dalam waktu polinomial menyiratkan ?
Jawaban:
Saya berasumsi bahwa P, NP, dan CoNP dalam pertanyaan tersebut adalah kelas bahasa, bukan kelas masalah janji. Saya menggunakan konvensi yang sama dalam jawaban ini. (Untuk berjaga-jaga, jika Anda berbicara tentang kelas masalah janji, maka jawabannya adalah afirmatif karena P = NP∩coNP sebagai kelas masalah janji setara dengan P = NP.)
Maka jawabannya adalah negatif di dunia yang relativized.
Pernyataan TFNP ⊆ FP dikenal sebagai Proposisi Q dalam literatur [FFNR03]. Ada pernyataan yang lebih lemah yang disebut Proposisi Q ' [FFNR03] bahwa setiap hubungan NPMV total dengan jawaban satu-bit ada di FP. (Di sini hubungan dengan jawaban satu bit berarti subset dari {0,1} * × {0,1}.) Mudah untuk melihat bahwa Proposisi Q relatif terhadap beberapa oracle menyiratkan Proposisi Q relatif terhadap oracle yang sama.
Fortnow dan Rogers [FR02] mempertimbangkan hubungan antara pernyataan P = NP∩coNP, Proposisi Q ', dan beberapa pernyataan terkait lainnya di dunia yang direlatifikasi. Secara khusus, Teorema 3.2 (atau Teorema 3.3) dalam [FR02] menyiratkan bahwa ada oracle relatif dimana P = NP∩coNP tetapi Proposisi Q 'tidak berlaku (dan oleh karena itu Proposisi Q tidak berlaku juga). Oleh karena itu, dalam dunia yang relatif, P = NP∩coNP tidak menyiratkan Proposisi Q; atau dengan mengambil kontrapositif, keberadaan hubungan TFNP yang tidak dapat dihitung dalam waktu polinomial tidak menyiratkan P ≠ NP∩coNP.
Referensi
[FFNR03] Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, dan John D. Rogers. Melompat ke fungsi. Informasi dan Komputasi , 186 (1): 90-103, Oktober 2003. DOI: 10.1016 / S0890-5401 (03) 00119-6 .
[FR02] Lance Fortnow dan John D. Rogers. Fungsi pemisahan dan satu arah. Kompleksitas Komputasi , 11 (3-4): 137–157, Juni 2002. DOI: 10.1007 / s00037-002-0173-4 .
sumber
sumber