11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In fact, ​ NP $\subseteq$ PSPACE . ​ ​ ​ ​ $\endgroup$ – user12859 Apr 22 '16 at 4:19
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 22 '16 at 7:21
16
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Strictly speaking, the polynomial in the second bullet needs to be chosen once and for all, it cannot depend on $x$ and $y$. ;) $\endgroup$ – Martin Berger Apr 22 '16 at 8:50
  • $\begingroup$ 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. $\endgroup$ – kasperd Apr 22 '16 at 13:26
  • 2
    $\begingroup$ @kasperd According to Wikipedia, EXPTIME is defined to be the decision problems that can be solved in $O(k^{p(|x|)})$. $\endgroup$ – tparker Apr 22 '16 at 16:55

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.