patternMajor
Why is NP in EXPTIME?
Viewed 0 times
whyexptimestackoverflow
Problem
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.
Solution
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
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.
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.
Context
StackExchange Computer Science Q#56323, answer score: 22
Revisions (0)
No revisions yet.