6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It can be shown that $\bf{NP \subseteq PSPACE \subseteq EXPTIME}$, so the answer is yes. $\endgroup$ – user340082710 Apr 18 '15 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$ – user340082710 Apr 19 '15 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 Ebert Apr 6 '17 at 17:25
10
$\begingroup$

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(|y|)$,
  • $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.

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.

$\endgroup$
  • $\begingroup$ Thanks. I have one question. In the 3-colourability example, what are $x$, $y$ and $R$? $\endgroup$ – Jung-Hyun Apr 19 '15 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$ – David Richerby Apr 19 '15 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$ – Jung-Hyun Apr 19 '15 at 0:55
  • $\begingroup$ No, because "finding $y$ in NP" doesn't mean anything. NP is a class of problems. $\endgroup$ – David Richerby Apr 19 '15 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$ – David Richerby Apr 6 '17 at 17:35

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.