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

Question

Das Existenzielle Theorie der Realität ist in PSPACE, aber ich weiß nicht, ob es ist PSPACE-Complete. Wenn ich glaube, dass es nicht der Fall ist, wie könnte ich es beweisen?

Allgemeiner im Allgemeinen, angesichts eines Problems in einer Komplexitätsklasse X, wie kann ich zeigen, dass es ist nicht X-Complete? Zum Beispiel, X könnte sein Np, PSPACE, Nachfolger.

Answer 1

Das Beweisen von $ x $ ist tatsächlich nicht $ pSpace $ -Complete (beispielsweise unter Reduzierungen der Polynomzeit) wäre äußerst schwierig.

Wenn $ p = pspace $, dann sind alle nicht trivialen (dh nicht $ varnothing $ und nicht $ sigma^{ star} $) und unendliche Probleme in $ PSPACE $ $ PSPACE $ -Complete unter Polynomzeitabbauungen sind . Da die existenzielle Theorie der Realität diese nicht triviale und unendliche Eigenschaft hat, beweist dies, dass es nicht $ Pspace $ -Complete würde $ p neq pSpace $ implizieren. (Sehen Die Antwort auf diese Frage zu csthory.se für eine Skizze des Beweises.)

Answer 2

Ein Problem in $ x $ beträgt nicht $ x $ -Complete, wenn es andere Probleme in $ x $ gibt, die nicht darauf reduziert werden können. Eine einfache Methode (aber möglicherweise nur wirksam für triviale Beispiele) würde beweisen, dass Ihr Problem auch in einer anderen Komplexitätsklasse $ y $ ist, so dass $ y subset x $.

Wenn Sie beispielsweise zeigen möchten, dass Ihr Problem nicht $ exptime $ vollständig ist, ist es ausreichend zu zeigen, dass es sich in $ p $ befindet, da $ p subetneq exptime $. Wenn Sie jedoch zeigen möchten, dass ein Problem nicht $ NP $ -Complete ist, ist es nicht unbedingt ausreichend zu zeigen, dass es in $ p $ ist, da nicht bekannt ist, ob $ p = np $.

Answer 3

Schauen Sie sich die akzeptierte Antwort auf diese Frage auf Mathoverflow an, Welche Techniken gibt es, um zu zeigen, dass ein Problem nicht NP-Vervollständigung ist?. Es beantwortet den Fall, wenn x = np.

Answer 4

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

Sei $ q $ ein Problem in einer Komplexitätsklasse $ x $ und $ s $ ist geschlossen. Das Beweisen, dass $ Q $ nicht $ x $ -Hard WRT $ Leq $ ist, ist gleichbedeutend mit der Trennung der Komplexitätsklasse, die durch Schließen von $ Q $ Wrt $ Leq $ erhalten wird. Wenn $ Q $ für eine andere Klasse $ y $ Wrt $ Leq $ schwierig ist, bedeutet dies, $ y $ von $ x $ zu trennen. Wie Sie wissen, gibt es nicht viele Trennergebnisse.

In Ihrem Fall $ x = mathsf {pspace} $, $ leq = leq^ mathsf {p} _m $ und $ y = mathsf {p} $.

Weil wir solche Ergebnisse im Moment nicht beweisen können (mit der möglichen Ausnahme von Ryan :), anstelle von Beweisen, dass $ Q $ nicht $ $ $ $ -Hard ist, zeigen wir, dass es sich in einer Komplexitätsklasse befindet, die es ist glaubte kleiner als $ x $ sein. Wenn Sie beispielsweise zeigen, dass $ mathrm {th} _ existiert ( mathbb {r,+, times, 0,1}) ist in $ mathsf {ph} $, dann wird es als a Starke Beweise für $ Q $ sind nicht $ $ $ $ -Hard. (Wenn Sie in der Sprache der Logiker ein bedingungsloses Ergebnis nicht nachweisen können, versuchen Sie, eine bedingte Annahme einer schwer zu beweisen, aber allgemein angenommenen Aussage wie $ mathsf {p} neq mathsf {pspace} $).