# 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 '16 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. – Raphael Apr 22 '16 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$. ;) – Martin Berger Apr 22 '16 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. – kasperd Apr 22 '16 at 13:26
• @kasperd According to Wikipedia, EXPTIME is defined to be the decision problems that can be solved in $O(k^{p(|x|)})$. – tparker Apr 22 '16 at 16:55