From the article: "Another interesting feature of NP problems is that a solution can be checked in polynomial time by a deterministic Turing machine. So, checking a solution of a NP problem is a P problem."<p>That's not just an interesting feature of NP problems, it's an alternate definition. You can define NP as the class of problems that have polynomial-time "verifiers". That is, the class of problems for which, given a candidate solution, you can determine in polynomial time whether that solution is correct.<p>Examples: given a proposed assignment to the variables of a boolean formula, you can check in P-time whether that assignment satisfies the formula. Given a proposed route through a set of cities, you can check in polynomial time whether that route has length less than K. Given a set S of integers, a subset of S, and a target T, you can check in P-time whether that subset sums up to T. Etc.<p>I find the "polynomial time verifier" definition of NP to be much clearer than the "solvable by a polynomial-time nondeterministic Turing machine" definition. They're exactly equivalent -- I don't know why the latter is so much more common.