Apakah kelengkapan CoNP menyiratkan kekerasan NP?

Apakah kelengkapan CoNP menyiratkan kekerasan NP? Secara khusus, saya memiliki masalah yang saya tunjukkan sebagai coNP-complete. Dapatkah saya mengklaim bahwa ini NP-hard? Saya menyadari bahwa saya dapat mengklaim kekerasan TNN, tetapi saya tidak yakin apakah terminologi itu standar.

Saya merasa nyaman dengan klaim bahwa jika masalah NP-lengkap milik coNP, maka NP = coNP. Namun, catatan kuliah ini menyatakan bahwa jika masalah NP-hard milik coNP, maka NP = coNP. Ini kemudian akan menyarankan bahwa saya tidak dapat mengklaim bahwa masalah saya adalah NP-hard (atau bahwa saya telah membuktikan coNP = NP, yang saya sangat ragukan).

Mungkin, ada yang salah dengan pemikiran saya. Pikir saya adalah bahwa masalah coNP-lengkap adalah NP-hard karena:

setiap masalah dalam NP dapat dikurangi menjadi komplemennya, yang akan menjadi milik TNP.
masalah komplemen di coNP mengurangi ke masalah lengkap-coNP saya.
jadi kami memiliki pengurangan dari setiap masalah dalam NP menjadi lengkap-TNP saya, jadi masalah saya NP-keras.

complexity-theory np-hard Austin Buchanan
sumber

dalam satu kata, tidak! setidaknya berdasarkan pengetahuan saat ini. pertanyaannya terkait erat dengan P =? NP (atau lebih tepatnya coNP =? NP yang juga terbuka). catat bahwa jika coNP ≠ NP terbukti maka P ≠ NP juga terbukti karena P ditutup dengan komplemen.

vzn

Jawaban:

Anda mengklaim bahwa setiap masalah dalam NP dapat dikurangi menjadi komplemennya , dan ini berlaku untuk pengurangan Turing, tetapi (mungkin) tidak untuk banyak-satu pengurangan. Pengurangan banyak-satu dari ke adalah fungsi poli-waktu sehingga untuk semua , iff . $L_1$ $L_2$ $f$ $x$ $x \in L_1$ $f(x) \in L_2$

Jika beberapa masalah di CoNp adalah NP-keras, maka untuk bahasa apapun akan ada fungsi polytime sehingga untuk semua , IFF . Karena berada dalam coNP, ini memberikan algoritma coNP untuk , menunjukkan bahwa NP coNP, dan NP coNP. Sebagian besar peneliti tidak berharap ini menjadi masalah, dan masalah dalam coNP mungkin bukan NP-hard. $L$ $M \in NP$ $f$ $x$ $x \in M$ $f(x) \in L$ $L$ $M$ $\subseteq$ $=$

Alasan kami menggunakan reduksi Karp daripada reduksi Turing adalah agar kami dapat membedakan antara masalah NP-hard dan coNP-hard. Lihat jawaban ini untuk detail lebih lanjut (Pengurangan Turing disebut reduksi Cook dalam jawaban itu).

Akhirnya, coNP-hard dan coNP-complete adalah terminologi standar, dan Anda bebas untuk menggunakannya.

Yuval Filmus
sumber

NP \overset{?}{=} coNP

$\text{NP} \overset{?}{=} \text{coNP}$

co

$\text{co}$

NP

$\text{NP}$

Itu benar, dan itu juga yang saya tunjukkan dalam jawabannya. Ketika saya menyatakan bahwa itu tidak benar untuk banyak-satu pengurangan, saya tidak bermaksud dalam arti logis, tetapi lebih dalam arti bahwa "pengurangan yang Anda pikirkan adalah pengurangan Turing tetapi bukan pengurangan banyak-satu" .

Yuval Filmus

Oh baiklah, ya itu mungkin masalahnya.

G. Bach

Terima kasih. Apa referensi yang bagus untuk ini? Khususnya untuk "NP = coNP di bawah pengurangan Cook, tetapi diperkirakan bahwa mereka berbeda dengan pengurangan Karp"?

Austin Buchanan

Percaya bahwa NP berbeda dari TNB agak luas. Kadang-kadang dikaitkan dengan Stephen Cook. Kekerasan NP itu sama dengan kekerasan BNP di bawah pengurangan Cook segera mengikuti dari definisi.

Yuval Filmus

$x \in L$ $\text{M}$ $x \notin \overline{L}$ $\text{M}$ $x$ $NP$

$\text{NP}$ $\text{coNP}$ $L \in \text{coNP}$ $\text{M}$

x \in L ⟺ \forall z \in {0, 1}^{p (| x |)} : M (x, z) = 1

$x \in L \iff \forall z \in \{0,1\}^{p(|x|)}:\text{M}(x,z) = 1$

$\overline{L}$ $\text{M'}$

x \in \bar{L} ⟺ \exists z \in {0, 1}^{q (| x |)} : M' (x, z) = 1

$x \in \overline{L} \iff \exists z \in \{0,1\}^{q(|x|)}:\text{M'}(x,z) = 1$

$\text{NP}$ $\text{M'}$ $\text{K}$ $\text{coNP}$ $\text{M}$ $\text{K}$ $\forall$ $\text{coNP}$ $\text{NP}$ $\text{M'}$ $0$ $x \in \text{K}$ $\exists$ $\forall$

Mungkin lebih abstrak: tidak jelas bagaimana membangun (dalam waktu polinomial) sebuah mesin yang mengenali dengan tepat unsur-unsur suatu bahasa, terlepas dari sertifikat apa yang menyertainya, dari sebuah mesin yang mengenali persis unsur-unsur bahasa yang memiliki beberapa sertifikat untuk itu, tetapi juga beberapa sertifikat tidak berfungsi.

G. Bach
sumber

Akan tetapi, yang mengejutkan, diketahui bahwa NL = coNL, NPSPACE = coNPSPACE, dan secara umum kelas-kelas non-deterministik yang ditentukan oleh kendala ruang ditutup dengan komplementasi. Ini adalah teorema Immerman-Szelepcsényi.

Yuval Filmus

Menarik, saya tidak tahu itu - tetapi intuisi di baliknya mungkin adalah cara yang selalu ada dengan kelas ruang: kita bisa menggunakan kembali ruang itu.

G. Bach

s

$s$

t

$t$

\log n

$\log n$

s

$s$

t

$t$