NP complete - solvable in non-deterministic polynomial time

StackOverflow https://stackoverflow.com/questions/20638165

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?

Était-ce utile?

La solution 2

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.

Autres conseils

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
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top