I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ It can be shown that $\bf{NP \subseteq PSPACE \subseteq EXPTIME}$, so the answer is yes. $\endgroup$– user340082710Commented Apr 18, 2015 at 23:49
-
$\begingroup$ In fact, one can show that SAT is in $\bf{PSPACE}$ by noting that we only require a polynomial (linear) amount of space by successively trying all possible truth assignments (we only need to keep track of a single assignment of variables). But since SAT is $\bf{NPC}$ we have that $\bf{NP \subseteq PSPACE}$. These arguments can be formalized, but I will leave it to someone else to do so. $\endgroup$– user340082710Commented Apr 19, 2015 at 0:00
-
$\begingroup$ I can understand that 3SAT, and therefore all of NP, is in EXPTIME. Because 3SAT runs in linear space. But how can all of PSPACE run in exponential time? $\endgroup$– Bjarke EbertCommented Apr 6, 2017 at 17:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Yes, every NP problem has an exponential-time algorithm. One definition of NP is the "succinct certificates" definition: a language $L$ is in NP if, and only if, there is a relation $R$ on strings such that:
- there is a polynomial $p$ such that, whenever $(x,y)\in R$, $|y|\leq p(|x|)$,
- $x\in L$ if, and only if, $(x,y)\in R$ for some $y$, and
- there is a deterministic Turing machine that decides if $(x,y)\in R$ in polynomial time or not.
So, to decide if $x\in L$, all you need to do is try all possible $y$s of length at most $p(|x|)$ to see if $(x,y)\in R$ for some $y$. There are exponentially many possible values of $y$ to try.
To see the intuition behind succinct certificates, consider 3-colourability. There, a certificate is a 3-colouring of the graph. To describe a 3-colouring needs just a constant number of bits to say what colour each vertex of the graph has, so the length of the certificate is bounded by a polynomial. Obviously, a graph is 3-colourable if, and only if, it has a 3-colouring. And if I claim to have a 3-colouring of a graph, you can check that in deterministic polynomial time: just make sure I didn't give the same colour to two adjacent vertices.
To get a succinct certificate for any NP-problem, use the definition that a problem is in NP if it's decided by a nondeterministic Turing machine in polynomial time. Use a description of an accepting run of that machine as the certificate.
answered Apr 19, 2015 at 0:15
-
$\begingroup$ Thanks. I have one question. In the 3-colourability example, what are $x$, $y$ and $R$? $\endgroup$ Commented Apr 19, 2015 at 0:44
-
2$\begingroup$ $x$ is the graph, encoded as a string; $y$ is a 3-colouring of the graph, also encoded as a string (e.g., "rggbrgrrr" listing the colours of each vertex in turn) and $R$ is the relation $\{(x,y)\mid x\text{ is a graph and $y$ is a 3-colouring of }x\}$. $\endgroup$ Commented Apr 19, 2015 at 0:47
-
$\begingroup$ aha.. Can I understand your answer like this? Every problem in NP have an exponential time algorithm because finding $y$ in NP takes an exponential time. $\endgroup$ Commented Apr 19, 2015 at 0:55
-
$\begingroup$ No, because "finding $y$ in NP" doesn't mean anything. NP is a class of problems. $\endgroup$ Commented Apr 19, 2015 at 8:46
-
1$\begingroup$ @BjarkeEbert Exponential time is usually taken to mean $\bigcup_{i\geq0}\mathrm{TIME}(2^{n^i})$. So, yes, $2^{x^2}$ would usually be described as "exponential", as distinct from $2^{2^x}$, which is "doubly-exponential". $\endgroup$ Commented Apr 6, 2017 at 17:35