# Why is NP in EXPTIME?

Is there an easy way to see why NP is in EXPTIME? It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be verified in polynomial time.

• In fact, ​ NP $\subseteq$ PSPACE . ​ ​ ​ ​
– user12859
Apr 22, 2016 at 4:19
• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. Apr 22, 2016 at 7:21

Any problem in NP is in EXPTIME because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine.

More formally, there are two main definitions of NP. One is that a language $L$ is in NP iff there is a relation $R$ such that

• there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$,
• given the string $x\#y$, we can determine in time polynomial in $|x\#y|$ whether $(x,y)\in R$, and
• $L = \{x\mid (x,y)\in R\}$.

So, if we have exponential time and we want to know if $x\in L$, we can just try all $|\Sigma|^{p(n)}$ possible values for~$y$ and see if $(x,y)\in R$ for any of those. That takes time $2^{O(p(n))}$, so $L\in\,$EXPTIME.

Alternatively, we can define NP as the set of languages decided by polynomial time nondeterministic Turing machines. In this case, suppose that $L$ is decided by machine $M$ in time $p(n)$ for some polynomial $p$, for inputs of length $n$. Then $M$ makes at most $p(|x|)$ nondeterministic choices while determining if $x\in L$. By examining $M$'s transition function, we can find a constant $k$ such that $M$ has at most $k$ nondeterministic choices at each step of the computation (independent of the input), so it has at most $k^{p(|x|)} = 2^{O(p(|x|))}$ different sequences of nondeterministic choices while reading input $x$. Given exponential time, we can simulate each of these possibilities one after another and see if any of them accepts.

• Strictly speaking, the polynomial in the second bullet needs to be chosen once and for all, it cannot depend on $x$ and $y$. ;) Apr 22, 2016 at 8:50
• What exactly is the definition of EXPTIME? I recall it as $O(k^{|x|})$, but your answer seems to assume $O(k^{p(|x|)})$. It is not obvious that the extra polynomial can be included without making it a different complexity class. Apr 22, 2016 at 13:26
• @kasperd According to Wikipedia, EXPTIME is defined to be the decision problems that can be solved in $O(k^{p(|x|)})$. Apr 22, 2016 at 16:55