Polynomial-Time Verification
Verification asks whether a proposed answer can be checked quickly, which is the defining feature of the class NP.
Checking versus finding
Verification is the act of confirming that a proposed solution is correct, as opposed to finding the solution from scratch. For many problems, checking is dramatically easier than solving. This gap between verifying and finding is the conceptual core of NP.
The certificate
A verifier receives the problem instance plus a certificate, a proposed proof that the answer is yes. If the verifier runs in polynomial time and accepts exactly the true yes-instances when given a valid certificate, the problem is in NP. The certificate must be polynomial in size, or checking it could not be fast.
Examples
- Sudoku: a filled grid is checked row by row in linear time
- Composite number: a nontrivial factor is verified by one division
- Graph coloring: an assignment of colors is checked edge by edge
- Hamiltonian cycle: a proposed cycle is traced in linear time
Why it defines NP
NP is exactly the set of problems with polynomial-time verifiers. This is equivalent to the nondeterministic machine definition: guessing the certificate is the nondeterministic step, and checking it is the deterministic verification. The two views describe the same class.
The deep question
If verification is easy, must finding also be easy? That is the P vs NP question restated. Intuitively, recognizing a good solution when shown one seems far easier than discovering it, which is why most believe P is not NP, though the belief is unproven.
Verification in the real world
The verify-easy, solve-hard asymmetry is the basis of much cryptography and of proof systems. A digital signature is hard to forge but easy to check; a mathematical proof is hard to find but (ideally) easy to verify. Interactive and probabilistically checkable proofs extend this idea in surprising directions.