Zeigen, dass ein Problem in X nicht X-Complete ist

18

Die existenzielle Theorie der Realitäten ist in PSPACE , aber ich weiß nicht, ob sie PSPACE-vollständig ist . Wenn ich glaube, dass es nicht der Fall ist, wie könnte ich es beweisen?

Wie kann ich generell nachweisen, dass es sich bei einem Problem der Komplexitätsklasse X nicht um X-Complete handelt ? Beispielsweise könnte X NP , PSPACE , EXPTIME sein .

Dave Clarke
quelle
Klar ist es nicht einfach und niemand kann eine Antwort für deinen allgemeinen Teil geben :-) Ich habe zu viele Probleme Ich weiß, dass sie NP sind, aber ich weiß nicht, dass sie NP-vollständig sind oder nicht (auch nicht zu viele andere Leute).

Antworten:

16

Tatsächlich wäre es äußerst schwierig, zu beweisen, dass nicht vollständig ist (beispielsweise unter Polynomzeitverkürzungen).P S P A C EXPSPACE

Wenn , dann werden alle nicht-trivial (dh nicht und nicht ) und unendliche Probleme in sind -komplette unter Polynom-Zeitverkürzungen. Da die existentielle Theorie der Realitäten diese nicht-triviale und unendliche Eigenschaft hat, würde der Beweis, dass sie nicht vollständig ist, implizieren . ( Eine Skizze des Beweises finden Sie in der Antwort auf diese Frage auf CSTheory.SE .)& Sigma; P S P A C E P S P A C E P S P A C E P P S P A C EP=PSPACEΣPSPACEPSPACE PSPACEPPSPACE

Ryan Williams
quelle
1
Sieht sicher so aus, als hätte ich mehr abgebissen, als ich sozusagen kauen kann.
Dave Clarke
11

Ein Problem in ist nicht vollständig, wenn es andere Probleme in die nicht darauf reduziert werden können. Eine einfache (aber möglicherweise nur dann wirksam auf triviale Beispiele) Methode würde beweisen , Ihr Problem ist auch in einigen anderen Komplexitätsklasse , so dass .X X Y Y XXXXYYX

Wenn Sie beispielsweise zeigen möchten, dass Ihr Problem nicht vollständig ist, reicht es aus, zu zeigen, dass es sich um , da . Wenn Sie jedoch zeigen möchten, dass ein Problem nicht vollständig ist, reicht es nicht aus, zu zeigen, dass es sich um , da nicht bekannt ist, ob ist oder nicht .EXPTIMEPN P P P = N PPEXPTIMENPPP=NP

Joe
quelle
3

Wie Ryan schrieb, ist es nicht einfach zu beweisen, dass ein Problem nicht schwer ist.

Sei ein Problem in einer Komplexitätsklasse und ist geschlossen für Reduktionen. Der Beweis , dass nicht ist -hard WRT entspricht die Komplexität Klasse Trennung erhalten durch Schließen des Nehmens WRT . Nun, wenn ist schwer für eine andere Klasse WRT , dann bedeutet das Trennen aus . Wie Sie wissen, gibt es nicht viele Trennungsergebnisse.X S Q X Q Q Y Y XQXSQXQQYYX

In Ihrem Fall ist , und .= P m Y = PX=PSpace≤=mPY=P

Da wir solche Ergebnisse derzeit nicht nachweisen können (mit der möglichen Ausnahme von Ryan :), anstatt zu beweisen, dass nicht hart ist, zeigen wir, dass es sich um eine Komplexitätsklasse handelt, von der angenommen wird , dass sie kleiner als . Wenn Sie zeigen zum Beispiel, dass ist in , dann wird es als starker Beweis für ergriffen werden nicht hart sein. (Wenn Sie in der Sprache der Logiker kein unbedingtes Ergebnis nachweisen können, versuchen Sie, ein bedingtes Ergebnis unter der Annahme einer schwer zu beweisenden, aber weit verbreiteten Aussage wie )X X T h ( R , + , x , 0 , 1 ) P H Q X PP S p a c eQXXTh(R,+,×,0,1)PHQXPPSpace

Kaveh
quelle