Bedeutet coNP-Vollständigkeit NP-Härte?

12

Bedeutet coNP-Vollständigkeit NP-Härte? Insbesondere habe ich ein Problem, von dem ich gezeigt habe, dass es coNP-vollständig ist. Kann ich behaupten, dass es NP-schwer ist? Mir ist klar, dass ich CoNP-Härte beanspruchen kann, aber ich bin nicht sicher, ob diese Terminologie Standard ist.

Ich bin mit der Behauptung einverstanden, dass NP = coNP ist, wenn ein NP-vollständiges Problem zu coNP gehört. In diesen Vorlesungsunterlagen heißt es jedoch, dass, wenn ein NP-hartes Problem zu coNP gehört, NP = coNP ist. Dies würde dann bedeuten, dass ich nicht behaupten kann, dass mein Problem NP-schwer ist (oder dass ich coNP = NP nachgewiesen habe, was ich sehr bezweifle).

Vielleicht stimmt etwas nicht mit meinem Denken. Meiner Meinung nach ist ein coNP-vollständiges Problem NP-schwer, weil:

  1. Jedes Problem in NP kann auf sein Komplement reduziert werden, das zu coNP gehört.
  2. Das Komplementproblem in CoNP reduziert sich auf mein CoNP-vollständiges Problem.
  3. Somit haben wir eine Reduktion von jedem Problem in NP auf mein CoNP-Complete, also ist mein Problem NP-schwer.
Austin Buchanan
quelle
mit einem wort, nein! Zumindest nach aktuellem Kenntnisstand. Die Frage steht in engem Zusammenhang mit P = & Dgr; NP (oder genauer gesagt mit coNP = & Dgr; NP, was ebenfalls offen ist). man beachte, dass wenn coNP ≠ NP bewiesen ist, P ≠ NP auch bewiesen ist, weil P unter Komplement geschlossen ist.
vzn

Antworten:

10

Sie behaupten, dass jedes Problem in NP auf sein Komplement reduziert werden kann , und dies gilt für Turing-Reduktionen, aber (wahrscheinlich) nicht für Viel-Eins-Reduktionen. Eine viel eine Reduktion von bis L 2 ist eine polytime Funktion f so dass für alle x , x L 1 iff f ( x ) L 2L1L2fxxL1f(x)L2 .

Wenn ein Problem in coNP NP-hart waren, dann für jede Sprache M N P würde es eine Funktion sein polytime f so dass für alle x , x M iff f ( x ) L . Da L in coNP ist, ergibt dies einen coNP-Algorithmus für M , der zeigt, dass NP coNP ist und somit NP = coNP. Die meisten Forscher erwarten nicht, dass dies der Fall ist, und daher sind Probleme bei der CoNP wahrscheinlich nicht NP-schwer.LMNPfxxMf(x)LLM=

Der Grund, warum wir Karp-Reduktionen anstelle von Turing-Reduktionen verwenden, besteht darin, dass wir zwischen NP-harten und coNP-harten Problemen unterscheiden können. Weitere Informationen finden Sie in dieser Antwort (Turing-Reduzierungen werden in dieser Antwort als Cook-Reduzierungen bezeichnet).

Schließlich sind coNP-hard und coNP-complete Standardbegriffe, die Sie frei verwenden können.

Yuval Filmus
quelle
"aber nicht für viele" - ist das nicht das Problem der Entscheidung ? = coNP genau, dass wir nicht wissen, ob es Karp-Reduktionen von einer ( Co ) NP-Sprache zu ihrer Ergänzung gibt? NP=?coNPcoNP
G. Bach
Das ist richtig und das zeige ich auch in der Antwort. Als ich feststellte, dass es nicht für viele Reduzierungen gilt, habe ich es nicht im streng logischen Sinne gemeint, sondern in dem Sinne, dass "die Reduktion, an die Sie denken, eine Turing-Reduktion ist, aber keine Viele-Eins-Reduktion". .
Yuval Filmus
Ach ja, das ist wahrscheinlich das Problem.
G. Bach
Vielen Dank. Was ist eine gute Referenz dafür? Insbesondere für "NP = coNP unter Cook-Reduktionen, aber es wird angenommen, dass es sich um unterschiedliche Karp-Reduktionen handelt"?
Austin Buchanan
Die Annahme, dass sich NP von coNP unterscheidet, ist ziemlich weit verbreitet. Manchmal wird es Stephen Cook zugeschrieben. Diese NP-Härte entspricht der coNP-Härte unter Cook-Reduktionen und ergibt sich unmittelbar aus der Definition.
Yuval Filmus
6

Das Problem mit dieser Argumentation ist der erste Schritt. Im deterministischen Fall können Sie mit einem TM M entscheiden, wenn Sie x ¯ L damit entscheiden können, weil die Art und Weise, dies zu tun, nur das Ausgangsbit von M umdrehen ist, da sein Ausgang nur von x abhängt (wenn wir Vergleiche mit der Verifier-Definition vonxLMxL¯Mx ).NP

Im nicht deterministischen Fall, in dem die Verifiziererdefinition verwendet wird, ist nicht bekannt, ob Sie einen Verifizierer aus einem coNP- Verifizierer oder umgekehrt erstellen können, und das Problem besteht darin, dass die Definitionen, die die Verifizierermaschinen erfüllen müssen, unterschiedliche Quantifizierer aufweisen. Lassen L coNP , dann haben wir ein Verifizierer DTMNPcoNPLcoNP , so dass:M

xLz{0,1}p(|x|):M(x,z)=1

Für ist der Prüfer M 'L¯M' müssen erfüllen

xL¯z{0,1}q(|x|):M'(x,z)=1

Warum können wir dann nicht einfach den Verifizierer M ' der Sprache K verwenden , um einen coNP- Verifizierer M für K zu erstellen ? Das Problem ist, dass der ∀- Quantifizierer einen coNP- Verifizierer benötigt. Die NP -verifier M‘ können Sie 0 für einig (falsches) Zertifikat auch für x K , so dass Sie nicht aus gehen können zu .NPM'KcoNPMKcoNPNPM'0xK

Vielleicht abstrakter: Es ist nicht klar, wie (in Polynomialzeit) eine Maschine erstellt werden soll, die genau die Elemente einer Sprache erkennt, unabhängig davon, welches Zertifikat sie enthält, und zwar von einer Maschine, die genau die Elemente einer Sprache erkennt, für die ein Zertifikat vorliegt es, aber für die auch einige Zertifikate nicht funktionieren.

G. Bach
quelle
4
Überraschenderweise ist jedoch bekannt, dass NL = coNL, NPSPACE = coNPSPACE und im Allgemeinen nicht deterministische Klassen, die durch Raumbeschränkungen definiert sind, unter Komplementierung geschlossen werden. Dies ist der Satz von Immerman-Szelepcsényi.
Yuval Filmus
Interessant, das wusste ich nicht - aber die Intuition dahinter ist wahrscheinlich so, wie es immer bei Raumklassen ist: Wir können den Raum einfach wiederverwenden.
G. Bach
@ G.Bach Nicht wirklich, nein. NL = co-NL wird ermittelt, indem gezeigt wird, dasss-t-non-connectivity ist in NL. Für größere Raumklassen (der Satz gilt mindestens nur für RaumLogn), Sie nutzen s-t- (Nicht-) Konnektivität im Konfigurationsdiagramm der betreffenden Turing-Maschine.
David Richerby