I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.

  • $\begingroup$ my understanding is that there are some problems in ExpSpace that can be solved in ExpTime and are not checkable in PTime... or is it an open question? maybe someone can clarify that... maybe will think of asking this separately... $\endgroup$ – vzn Dec 23 '13 at 16:57

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.

  • $\begingroup$ any reason particularly for using ⊊ over ⊂? $\endgroup$ – John D Apr 25 at 10:13
  • $\begingroup$ By $\subsetneq$ I mean "strict containment". This is also what $\subset$ usually means, but I like the former more, since it's more explicit. $\endgroup$ – Shaull Apr 25 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.