patternModerate
Are there any problems in complexity class EXP that are not in NP?
Viewed 0 times
areanyexpproblemsthatthereclasscomplexitynot
Problem
I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.
Solution
First of all, we don't know whether $NP=EXP$ or not. So the initial answer is "it is an open question".
However, we strongly believe (and there are supporting evidence) that $NP\neq EXP$. In fact, we believe that $NP\neq PSPACE$ and that $PSPACE\neq EXP$ (that is, there is a strict containment $NP\subsetneq PSPACE \subsetneq EXP$).
Since you are looking into problems that cannot (to our knowlendge) be verified in polynomial time, you can start with any PSPACE complete problem. For example, TQBF, or $ALL_{NFA}$. If you want EXP-complete problems, there are examples here.
However, we strongly believe (and there are supporting evidence) that $NP\neq EXP$. In fact, we believe that $NP\neq PSPACE$ and that $PSPACE\neq EXP$ (that is, there is a strict containment $NP\subsetneq PSPACE \subsetneq EXP$).
Since you are looking into problems that cannot (to our knowlendge) be verified in polynomial time, you can start with any PSPACE complete problem. For example, TQBF, or $ALL_{NFA}$. If you want EXP-complete problems, there are examples here.
Context
StackExchange Computer Science Q#19176, answer score: 12
Revisions (0)
No revisions yet.