Existem problemas na classe de complexidade EXP que não estão no NP?

Não consigo conceber nenhum problema que possa ser resolvido em tempo exponencial, mas não possa ser verificado em tempo polinomial.

Primeiro de tudo, não sabemos se $NP=EXP$ou não. Portanto, a resposta inicial é "é uma pergunta em aberto".

No entanto, acreditamos firmemente (e existem evidências) que $NP\neq EXP$. De fato, acreditamos que$NP\neq PSPACE$ e essa $PSPACE\neq EXP$ (ou seja, existe uma restrição estrita $NP\subsetneq PSPACE \subsetneq EXP$)

Como você está analisando problemas que não podem (a nosso conhecimento) ser verificados em tempo polinomial, você pode começar com qualquer problema completo do PSPACE. Por exemplo, TQBF ou$ALL_{NFA}$. Se você deseja problemas com a EXP completa, existem exemplos aqui .