NP complete - solvable in non-deterministic polynomial time

Question

It is written in a book that --"If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A" . But as far I know 'yes' -answer for NP complete problems can be "verified" in polynomial time. I am really confused. Can a NP-complete problem be "solved" using non-deterministic polynomial time algorithm?

Answer 1

Finding the solution to an NP-complete problem can be done in polynomial time on a non-deterministic Turing machine. Given a candidate solution of an NP-complete problem, it can be verified whether it is indeed a solution or not, i.e. checked, in polynomial time on a deterministic Turing machine.

So the difference is in finding a solution and checking a solution. The former usually requires some kind of search for NP-complete problems while the latter is just verifying the assignments to your variables.

Answer 2

The two things are basically identical and are based on two different though equivalent definition of NP.

Every problem (language) in NP must be:

1. Verified in polynomial time by a deterministic turing machine. (given a problem and a 'verification', you can answer if the verification is correct for the problem in a polynomial time).
   Example: Given a graph, and you want to check if there is a hamiltonian path in it - the verifier can be the path. You can easily check if the path is indeed hamiltonian once you have it.
2. Solved in polynomial time by a non deterministic turing machine. (there exists non deterministic Turing Machine M that can solve the problem polynomially)

Since by definition of NP-Complete - a problem is NP Complete if it is NP-Hard AND in NP, every NP-Complete problem is also NP - and both are correct.

---

Note that those two claims are basically based on the two equivalent definitions for NP:

1. A language L is in NP if for each x in L there is a word z such that |z| is polynomial in |x|, and there exists some deterministic turing machine that runs in polynomial time M - such that for each x and its matching z,: M(x,z) = true if and only if x is in L
2. A problem is in NP if there is a non deterministic turing machine that can solve the problem in polynomia time. Formally, a language L is in NP if there is a non deterministic turing machine such that M(x) = true if and only if x is in L