Hat das coNP-complete-Problem ein Zertifikat für subexponentielle Größe?

13

Angenommen, NP! = CoNP, dann gibt es kein polynomiales Größenzertifikat für das coNP-vollständige Problem. Aber was ist mit subexponentiellen Größenbescheinigungen? Gibt es insbesondere für coSAT einen subexponentiellen Größenbeweis, um zu beweisen, dass eine Formel nicht befriedigend ist? Wenn nicht, was ist der negative Beweis? Vielen Dank

cc.complexity-theory proof-complexity Xi Wu
quelle

cstheory.stackexchange.com/questions/22022/…

Igor Shinkar

12

Dies ist das Thema der Beweis Komplexität, dh die Größe von Zertifikaten für den Problem ( ). $\mathbf{co\text{-}NP}\text{-}complete$ $TAUT$ $= coSAT$

Die kurze Antwort lautet: Es ist offen.

Auf der negativen Seite, können wir nicht einmal zeigen , dass es nicht Polygrßenverteilung Widerlegungen für unerfüllbar Formeln (geschweige denn die allgemeine Frage zu zeigen , dies für ein beliebiges Proof - System, ein Satz Proof - System kann für als nichtdeterminismus gedacht werden ). $Frege$ $TAUT$

Die Frage ist auch äquivalent zu . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

Kaveh
quelle

1

Vielen Dank. Was ist dann der allgemeine Glaube an dieses Problem? Ich denke, die Community hat einige "Vermutungen" über das Ergebnis angestellt.

Xi Wu

Ich habe keine gute Antwort und kann mich nicht daran erinnern, Vermutungen darüber gehört zu haben. Das einzige, was mir derzeit einfällt, ist, dass einige Experten es für plausibel halten, dass EF (Extended-Frege) ein optimaler Beweis ist System, aber EF wäre ein optimales Beweissystem, selbst wenn einige Theoreme keine subexponentiellen EF-Beweise haben (dh

). Es gibt Forscher, die sogar

plausibel halten, und es gibt andere, die

denken

c o N P ⊈ N T i m e (2^{o (n)})

$\mathbf{coNP} \not \subseteq NTime(2^{o(n)})$

c o N P = N P

$\mathbf{coNP}=\mathbf{NP}$

).

c o N P ⊈ N T i m e (2^{o (n)})

$\mathbf{coNP} \not \subseteq NTime(2^{o(n)})$

Kaveh

7

Eine mögliche Folgerung daraus wäre, dass von Ryan Williams Ergebnis (da Sie hätten dann einen Co-nichtdeterminismus für CircuitSAT in der Zeit läuft schneller als exponentiell). Keine wirklich negativen Beweise, aber dennoch ... $NEXP \nsubseteq P/poly$

Ramprasad
quelle

Vielen Dank. Ich neige dazu, Ihre Antwort so zu interpretieren, dass die Schwierigkeit, das coNP-vollständige Problem zu zeigen, einen subexponentiellen Größenbeweis hat, weil wir dann eine schöne Trennung haben.

Xi Wu

Hat das coNP-complete-Problem ein Zertifikat für subexponentielle Größe?

Antworten: