[Solved]: Does every problem in NP have an exponential time algorithm?

Problem Detail: 

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.

Asked By : Jung-Hyun

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41555