The two things are basically identical and are based on two different though equivalent definition of NP.
Every problem (language) in NP must be:
- 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.
- 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:
- 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
- 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