Past exam question: 2081 Chaitra (Regular), Q5(b)
Open in the Padhaiko appQuestion
Explain NP-Complete problems.
Solution
Definition, Properties, and Practical Significance of NP-Complete: The class NP-Complete (NPC) comprises the computationally hardest problems in the class NP (Nondeterministic Polynomial time).
A decision problem is defined as NP-Complete if it satisfies two conditions:
- : A given candidate solution (certificate) can be verified deterministically in polynomial time .
- is NP-Hard: Every problem is polynomial-time reducible to (). That is, an efficient polynomial-time algorithm for would immediately yield a polynomial-time algorithm for every problem in NP.
Cook–Levin Theorem: Proved in 1971 that the Boolean Satisfiability Problem (SAT) is NP-Complete, establishing the foundation of computational complexity theory.
Representative NP-Complete Problems:
- 3-SAT (3-Conjunctive Normal Form Satisfiability)
- Traveling Salesperson Decision Problem
- Vertex Cover and Independent Set
- Hamiltonian Circuit Problem
- Subset Sum Problem
Answer:
An NP-Complete problem belongs to NP and is NP-Hard (every problem in NP reduces to it in polynomial time). First proven for SAT by the Cook–Levin Theorem, solving any NP-Complete problem in polynomial time would imply .