Dapatkah menemukan saksi menjadi NP-hard bahkan jika kita sudah tahu ada?

Contoh umum masalah NP-hard (klik, 3-SAT, vertex cover, dll.) Adalah tipe di mana kita tidak tahu apakah jawabannya "ya" atau "tidak" sebelumnya.

Misalkan kita memiliki masalah di mana kita tahu jawabannya adalah ya, lebih jauh lagi kita dapat memverifikasi saksi dalam waktu polinomial.

Bisakah kita selalu menemukan saksi di waktu polinomial? Atau bisakah "masalah pencarian" ini menjadi NP-hard?

TFNP adalah kelas fungsi multinilai dengan nilai yang diverifikasi secara polinomi dan dijamin ada.

Ada masalah di TFNP yaitu FNP-lengkap jika dan hanya jika NP = co-NP, lihat Teorema 2.1 di:

Nimrod Megiddo dan Christos H. Papadimitriou. 1991. Tentang fungsi total, teorema keberadaan dan kompleksitas komputasional. Teor Komputasi. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016 / 0304-3975 (91) 90200-L

dan referensi [6] dan [11] di dalam. PDF tersedia di sini .

Tidak, Anda tidak selalu dapat menemukan solusi dalam waktu polinomial, bahkan jika Anda tahu ada solusinya.

Menurut Khanna, Linial, dan Safra [1] (lihat paragraf ke-3), sudah mengikuti dari karya klasik 1972 oleh Karp bahwa pewarnaan grafik 3-warna dengan 3 warna adalah NP-hard. (Pekerjaan mereka memperluas ini untuk menunjukkan bahwa grafik 4-warna 3-warna masih NP-keras).

Perhatikan bahwa ini tidak bertentangan dengan jawaban Rahul Savani . Ini karena untuk semua hubungan biner dalam FNP, kita harus dapat memverifikasi dalam waktu polinomial jika P ( x , y ) ada dalam relasi. Mengingat bahwa memutuskan apakah grafik 3-warna dengan 3 warna adalah NP-lengkap, kecil kemungkinannya untuk menemukan 4-warna dalam grafik 3-warna adalah dalam FNP karena kami tidak dapat memverifikasi validitas input x dalam waktu polinomial . Dengan demikian, tidak ada kontradiksi dengan hasil Megiddo-Papadimitriou.$P$$P(x,y)$$x$

[1] Khanna, Sanjeev, Nathan Linial, dan Shmuel Safra. "Pada kekerasan mendekati angka berwarna." Teori dan Sistem Komputasi, 1993., Prosiding Simposium Israel ke-2 tentang. IEEE, 1993.

Jika hubungan-NP adalah NP-keras sehubungan dengan
pengurangan Turing hanya waktu polinomial waktu-bersama co-nondeterministic, maka$\: NP = coNP \;$.




Bukti:



Jika suatu hubungan NP adalah NP-hard sehubungan dengan yes-answer-only
co-nondeterministic pengurangan waktu Turing, maka:

Mari menjadi seperti hubungan keras, dan biarkan M ' menjadi co-nondeterministic polinomial-waktu pengurangan Turing ya-jawaban-hanya dari S A T ke R .$R$$M'$$SAT$$R$$\:$Biarkan menjadi algoritma coNP yang diberikan oleh: $M$
$\;$Coba parsing dugaan anti- sertifikat ke dalam sertifikat dan tanggapan orang dalam.
$\;$Jika gagal maka output YA, jika tidak coba jalankan pada anti-sertifikat batin dengan memberi $M'$
$\;$ respons yang sama seperti yang diberikan sebelumnya untuk kueri-ulang dan menggunakan respons dari
$\;$ anti-sertifikat (luar) untuk semua pertanyaan oracle lainnya. $\:$Jika akan membuat lebih berbeda $M'$
$\;$kueri daripada jumlah respons atau kueri mana pun tidak akan terkait oleh ke $R$
$\;$respons kueri atau akan menampilkan YA, M menghasilkan YA, atau M menghasilkan TIDAK. Karena menjadi oracle untuk R hanya memaksakan kondisi independen pada respons oracle dan M ′ adalah pengurangan yes-answer-only, pasangan respons-respons yang dihasilkan oleh M ′ dan anti-sertifikat yang valid selalu dapat diperluas ke oracle untuk R , jadi M memecahkan S A $M'$$M$$M$
$R$
$M'$$M'$
$R$$M$$SAT\hspace{-0.02 in}$.
Jadi$\: SAT\in coNP \;$.
Karena adalah N P -hard sehubungan dengan pengurangan waktu polinomial deterministik,$SAT$$NP$$\: NP\subseteq coNP \;$.
Dengan simetri,$\: coNP \subseteq NP \;$. $\;\;\;\;$ Jadi $\: NP = coNP \;$.


Oleh karena itu, jika hubungan-NP adalah NP-keras sehubungan dengan yes-answer-only
co-nondeterministic pengurangan waktu Turing, maka$\: NP = coNP \;$.

Ini sedikit tergantung pada interpretasi yang tepat dari pertanyaan Anda, tetapi saya pikir skenario Anda dapat secara umum digambarkan sebagai masalah 'KOMPUTE Y' di mana diberikan beberapa algoritma waktu polinomial yang ditetapkan secara universal dan polinomial p , masukan ⟨ x , 1 n ⟩ , keluaran a string y ∈ { 0 , 1 } p ( n ) , sehingga T ( x , y , 1 n ) menghasilkan 1, dan y selalu ada untuk semua kemungkinan x .$T$$p$$\langle x, 1^n \rangle$$y \in \{0,1\}^{p(n)}$$T(x,y,1^n)$$y$$x$

Satu pertanyaan kemudian mungkin apakah algoritma waktu polinomial untuk 'KOMPUTE Y' menyiratkan $P = NP$

Dalam kasus ini, anggap Anda dapat memecahkan (katakanlah) 3SAT dalam waktu polinomial dengan jumlah panggilan konstan ke oracle yang memecahkan 'COMPUTE Y', yaitu beberapa algoritma mana A ( ϕ ) = 1 iff ϕ memuaskan, $A$$A(\phi) = 1$$\phi$ sebaliknya. Balikkan bit keluaran untuk mendapatkan ˉ A , sebuah algoritma di mana ˉ A ( ϕ ) = 0 iff ϕ memuaskan dan ˉ A ( ϕ ) = 1 jika$A(\phi)=0$$\bar{A}$$\bar{A}(\phi) = 0$$\phi$$\bar{A}(\phi) = 1$$\phi$ tidak memuaskan.

$\bar{A}$$y$$T$$NP = coNP$

$NP = coNP$$NP$$k$$NP$