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

7

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

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:

10

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 ).NPEXPNPPSPACEPSPACEEXPNPPSPACEEXP

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 .ALLNFA

Shaull
quelle