Algorithms / Np Npc Proofs
Least You Need to Know: NP, NP-Completeness Proofs, and Certificate-Based Reasoning
Exam questions on NP and NP-completeness are mostly about precise definitions. You need to separate fast verification from fast solving, know the standard two-part proof template, and move carefully between optimization problems and their decision versions.
The least you need to know
- A language is in `NP` if yes-instances have certificates that can be verified in polynomial time.
- To prove a problem is NP-complete, you usually show it is in `NP` and that a known NP-complete problem reduces to it in polynomial time.
- A polynomial-time algorithm for any NP-complete problem would imply polynomial-time algorithms for all problems in `NP`.
- Optimization problems are often analyzed through related decision versions in complexity proofs.
- Certificates justify membership in `NP`; reductions justify NP-hardness.
Key notation
P
decision problems solvable in polynomial time
NP
decision problems with polynomial-time verifiable yes-certificates
NPC
problems that are both in NP and NP-hard
Tiny worked example
- For **Vertex Cover**, the decision version asks whether there is a cover of size at most `k`.
- A certificate is the proposed set of vertices.
- Verification checks the set size and whether every edge touches the set.
- NP-completeness then needs a reduction from a known NP-complete problem, not just a verifier.
Common mistakes
- Students often say a problem is in NP because they can describe a brute-force search, but NP is about polynomial-time verification.
- Saying a problem is hard is not enough; the reduction direction has to come from a known hard problem.
- Optimization and decision versions are related, but they are not literally the same object in a proof.
How to recognize this kind of problem
- The prompt asks for the standard template of an NP-completeness proof.
- A proposed solution can be checked quickly even though finding one seems difficult.
- The problem statement includes a threshold parameter such as `k`, budget, or size bound.