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

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