# Does every problem in NP have an exponential time algorithm?

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.

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

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.

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