Bisakah kita membuat pengurangan Karp dari pengurangan Cook antara masalah NP?

Kami telah memiliki beberapa pertanyaan tentang hubungan pengurangan Cook dan Karp . Jelas bahwa pengurangan Cook (pengurangan Turing polinomial-waktu) tidak mendefinisikan gagasan yang sama tentang kelengkapan NP seperti pengurangan Karp (pengurangan polynomial-time-one-one), yang biasanya digunakan. Secara khusus, pengurangan Cook tidak dapat memisahkan NP dari co-NP bahkan jika P NP. Jadi kita tidak harus menggunakan pengurangan Cook dalam bukti reduksi khas.$\neq$

Sekarang, siswa menemukan karya peer-review [1] yang menggunakan pengurangan Cook untuk menunjukkan bahwa masalah adalah NP-hard. Saya tidak memberi mereka skor penuh untuk pengurangan yang mereka ambil dari sana, tapi saya ingin tahu.

Karena pengurangan Cook memang mendefinisikan gagasan kekerasan yang sama dengan pengurangan Karp, saya merasa mereka harus dapat memisahkan P dari resp NPC. co-NPC, dengan asumsi P NP. Secara khusus, (sesuatu seperti) yang berikut ini harus benar:$\neq$

$\qquad\displaystyle L_1 \in \mathrm{NP}, L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1 \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ .

Nugget penting adalah bahwa $L_1 \in \mathrm{NP}$ sehingga ketidakpekaan yang disebutkan di atas dielakkan. Kita sekarang "tahu" - dengan definisi NPC - $L_2 \leq_{\mathrm{Karp}} L_1$ .

Seperti yang telah dicatat oleh Vor , tidak semudah itu (notasi disesuaikan):

Misalkan $L_1 \in \mathrm{NPC}_{\mathrm{Cook}}$ , lalu menurut definisi, untuk semua bahasa $L_2 \in \mathrm{NPC}_{\mathrm{Karp}} \subseteq \mathrm{NP}$ kami miliki $L_2 \leq_{\mathrm{Cook}} L_1$ ; dan jika implikasi di atas benar maka $L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ dan karenanya $\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}}$ yang masih merupakan pertanyaan terbuka.

Mungkin ada perbedaan lain antara kedua NPC tetapi co-NP.

Jika gagal, apakah ada kriteria (non-sepele) yang diketahui ketika memiliki Cook-reduksi menyiratkan kekerasan Karp-NP, yaitu kita tahu predikat dengan$P$

$\qquad\displaystyle L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1, P(L_1,L_2) \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ ?

1. On Complexity of Multiple Sequence Alignment oleh L. Wang dan T. Jiang (1994)

ini merupakan masalah TCS yang umumnya terbuka yang sedang diteliti saat ini apakah kondisi yang tepat pengurangan Cook & Karp adalah setara dan tampaknya terkait erat dengan NP terbuka =? pertanyaan TNP & pemisahan kelas kompleksitas lainnya misalnya E =? NE (wrt sparse languages).

berikut adalah dua makalah penelitian tentang masalah ini & petunjuk lebih lanjut tentang tcs.se melalui pertanyaan serupa:

• Apakah Masak dan Karp Pernah Sama? Beigel, Fortnow

• Cook vs. Karp-Levin: Gagasan Seperating Sepenuhnya Jika NP Tidak Kecil (1995) Lutz, Mayordomo

• banyak satu pengurangan vs pengurangan Turing untuk mendefinisikan NPC , tcs.se

Secara umum, untuk secara mekanis mengubah masalah Cook-complete menjadi masalah Karp-complete, pasti ada sesuatu yang istimewa dengan bahasa itu sendiri.

Misalnya, bahkan versi pengurangan Cook yang sangat terbatas, yaitu reduksi negatif (reduksi ke satu contoh seperti Karp, minta jawaban, lalu negasikan), akan membutuhkan sesuatu yang khusus dalam bahasa agar mudah diubah menjadi pengurangan Karp standar.$L$

Kita dapat mengatakan bahwa jika memiliki properti berikut :$L$

Dengan contoh apa pun , kita dapat, dalam waktu polinomial, menghasilkan , sehingga .$x$$x'=f(x)$$L(x)\neq L(x')$

Jadi kita dapat memiliki pengurangan Karp standar dengan mengurangi pertama ke dengan reduksi negatif, kemudian output .$g(x)$$f(g(x))$

Seperti yang Anda lihat, properti ini biasanya tidak terlihat dalam teori kompleksitas, teori komputabilitas. Sebagai kesimpulan, sangat tidak mungkin untuk dapat mengubah Cook menjadi Karp.