Proving NP-Completeness
← Back to Polynomial-Time Reductions
To prove a problem X is NP-Complete: (1) show X is in NP (solutions can be verified in polynomial time), and (2) reduce a known NP-Complete problem to X in polynomial time. This shows X is at least as hard as the known NP-Complete problem.