Gibt es Probleme in der Komplexitätsklasse EXP, die nicht in NP sind?

Ich kann mir kein Problem vorstellen, das in exponentieller Zeit gelöst werden kann, aber nicht in Polynomzeit überprüft werden kann.

complexity-classes Christopher
quelle

Ich verstehe, dass es in ExpSpace einige Probleme gibt , die in ExpTime gelöst werden können und in PTime nicht überprüfbar sind ... oder ist es eine offene Frage? Vielleicht kann jemand klarstellen, dass ... vielleicht wird er darüber nachdenken, dies separat zu fragen ...

vzn

Antworten:

Zunächst wissen wir nicht, ob oder nicht. Die erste Antwort lautet also "es ist eine offene Frage". $NP=EXP$

Wir sind jedoch der festen Überzeugung (und es gibt Belege dafür), dass . Tatsächlich glauben wir, dass und ( es gibt eine strikte Eindämmung ). $NP\neq EXP$ $NP\neq PSPACE$ $PSPACE\neq EXP$ $NP\subsetneq PSPACE \subsetneq EXP$

Da Sie sich mit Problemen befassen, die (nach unserem Kenntnisstand) nicht in Polynomzeit überprüft werden können, können Sie mit jedem vollständigen PSPACE-Problem beginnen. Zum Beispiel TQBF oder . Wenn Sie EXP-vollständige Probleme wollen, gibt es Beispiele hier . $ALL_{NFA}$

Shaull
quelle