PCP-Theorem und Beweiskomplexität?

8

Es ist bekannt , dass , wenn P=NP dann CoNP=PCP[O(log(n)),O(1)] . Es ist auch bekannt, dass NEXP=PCP[poly(n),poly(n)]. Es scheint, dass PCP uns nicht sagen kann, welche natürlichen Probleme nicht in NP . Ich frage mich, ob es möglich ist, die PCP-Charakterisierung zu verwenden, um CoNP von zu trennen NP.

Was sind die besten Grenzen für die Zufälligkeitskomplexität r(n) und die Abfragekomplexität q(n) so dass das Tautologieproblem in PCP[O(r(n)),O(q(n))] ?

Mohammad Al-Turkistany
quelle
6
Es ist bekannt, dass NEXP = PCP [Poly (n), O (1)] als Folge des PCP-Theorems. Siehe z. B. die Einführung von Or Meirs Artikel
Tsuyoshi Ito
1
Sie erwähnen die Komplexität des Beweises im Titel (und in den Original-Tags). Hängt die rechnerische Komplexität des Tautologieproblems mit der Komplexität der Beweise zusammen?
Tsuyoshi Ito
Ja, wenn P = CoNP, dann hätte Tautologies kurze Beweise.
Mohammad Al-Turkistany
@Ito untersucht die Komplexität von Beweisen normalerweise Beweissysteme, die Aussagen-Tautologien etablieren. Jedes Beweissystem kann als nicht deterministischer Algorithmus für das Tautologieproblem angesehen werden. Beweiskomplexität ist also die Untersuchung nicht deterministischer Algorithmen für das Tautologieproblem.
Iddo Tzameret
@turkistany, du meintest NP = coNP.
Iddo Tzameret

Antworten:

12

N P c o N P.coNPPCP[o(n),q]NPcoNP

Dana Moshkovitz
quelle
Eigentlich denke ich, dass das eher ein Glück als ein Unglück sein könnte. Wenn es so einfach wäre, sie zu trennen, würde die gesamte Community ziemlich albern aussehen, wenn sie es vorher nicht entdeckt hätte.
Joe Fitzsimons
4
Es ist nicht nur so, dass solche Ergebnisse nicht bekannt sind, sie sind wahrscheinlich nicht wahr. Im Allgemeinen aus dem gleichen Grund glauben wir glauben wir , dass Nicht-Determinismus nicht wirklich Hilfe Tautologien zu lösen. Eine natürliche Annahme ist also, dass dieses Tautologieproblem nicht in nicht deterministischer Zeit (oder vielleicht sogar nicht in Zeit ) gelöst werden kann, was implizieren würde, dass es ist nicht in . 2 n o ( 1 ) 2 o ( n ) P C P [ n o ( 1 ) , p o l y ( n ) ]coNPNP2no(1)2o(n)PCP[no(1),poly(n)]
Boaz Barak
1
@ Boaz, das ist eine schöne Antwort. Könnten Sie es verschieben und eine separate Antwort geben?
Mohammad Al-Turkistany
12

Ich denke, das folgende Papier wird helfen: Polylogarithmisch-runde interaktive Beweise für coNP kollabieren die exponentielle Hierarchie

Es besagt, dass sofern die exponentielle Hierarchie nicht zusammenbricht. ( ist die Klasse von Sprachen mit beweglichen interaktiven Beweisen.)I P [ k ] kcoNPIP[logO(1)n]IP[k]k

In Bezug auf die natürliche Beziehung zwischen interaktiven und wahrscheinlich überprüfbaren Beweisen denke ich, dass das obige Ergebnis helfen muss.

Ich schlage auch vor, einen Blick auf ein neues Probenahmeprotokoll und Anwendungen zu werfen, um kryptogaphische Primitive auf der Härte von NP zu basieren .

MS Dousti
quelle
Könnten Sie bitte die Relevanz des zweiten Papiers erläutern?
Iddo Tzameret
Eine informelle Einführung in das zweite Papier finden Sie hier . Der Satz "Alle bekannten (sogar Multi-Prüfer-) Beweissysteme für Co-NP erfordern Prüfer mit # P-Komplexität" ist das Herzstück dessen, was sie mit der aktuellen Diskussion in Verbindung bringt.
MS Dousti