Complexity Classes P, NP, NP-Complete & Reductions
“Deterministic vs non-deterministic polynomial time, polynomial certificates, Cook-Levin theorem, and reduction chains.”
1.The Formal Anatomy of Complexity Classes
§ 5.1.Computational complexity categorizes problems based on the inherent resource requirements (time and space) of their algorithms:
1. Class P (Polynomial Time):
The class of languages decidable by a Deterministic Turing Machine in time O(n^k) for some constant k. Examples: Shortest Paths, MST, Sorting, Linear Programming.
2. Class NP (Nondeterministic Polynomial Time):
The class of decision problems for which a 'YES' answer has a polynomial-length certificate that can be verified by a deterministic algorithm in polynomial time.
Alternatively: Decidable by a Nondeterministic Turing Machine in polynomial time.
3. Class co-NP:
Languages whose complement is in NP. Example: TAUTOLOGY (verifying that a boolean formula is true for ALL truth assignments).
4. NP-Hard:
A problem X is NP-Hard if for every language L in NP, L <=_p X. NP-Hard problems need not be in NP (they can even be undecidable, like the Halting Problem).
5. NP-Complete:
A problem X is NP-Complete if: (1) X in NP, and (2) X is NP-Hard.
2.Polynomial-Time Reductions & Karp's 21 Reductions
§ 5.2.A polynomial-time reduction from language A to language B (A <=_p B) is a polynomial-time computable function f such that for every input string x:
x in A iff f(x) in B.
Fundamental Theorems of Reductions:
1. If A <=_p B and B in P, then A in P.
2. If A <=_p B and A notin P, then B notin P.
3. If A <=_p B and B <=_p C, then A <=_p C (Transitivity).
4. If A is NP-Complete, and A <=_p B with B in NP, then B is NP-Complete.
The Canonical Reduction Chain:
- Circuit-SAT (Cook-Levin Theorem, base of hierarchy)
- Circuit-SAT <=_p 3-SAT
- 3-SAT <=_p Independent Set (construct gadgets with 3 vertices per clause)
- Independent Set <=_p Vertex Cover (in graph G=(V, E), S is an independent set iff V setminus S is a vertex cover)
- Independent Set <=_p Clique (S is an independent set in G iff S is a clique in complement graph bar{G})
- 3-SAT <=_p Subset Sum <=_p Partition <=_p 0/1 Knapsack
- Hamiltonian Cycle <=_p Traveling Salesperson Problem (TSP)
3. Worked Problem: Directionality & Consequences of Reductions
Carefully read whether problem A reduces to problem B (A <=_p B) or vice versa. If an NP-complete problem reduces to X, X is at least as hard as NP.
Problem: Let P1 and P2 be two decision problems. Suppose P1 is known to be NP-Complete. Consider the following statements:
S1: If P1 <=_p P2, then P2 is NP-Hard.
S2: If P2 <=_p P1, then P2 is NP-Complete.
S3: If P1 <=_p P2 and P2 in P, then P = NP.
S4: If P2 <=_p P1 and P2 in P, then P = NP.
Determine the truth value of each statement.
Step 1: Analyze S1:
By definition, if a known NP-Complete problem P1 reduces to P2 in poly-time (P1 <=_p P2), then every problem in NP reduces to P2 via P1. Therefore P2 is NP-Hard.
S1 is TRUE.
Step 2: Analyze S2:
P2 <=_p P1 means P2 is at most as hard as P1. For example, the trivial problem 'Is 2 + 2 = 4?' reduces to 3-SAT, but it is in P, NOT NP-Complete.
S2 is FALSE.
Step 3: Analyze S3:
If P1 <=_p P2 and P2 in P, then P1 in P. Since P1 is NP-Complete, this implies every problem in NP is solvable in polynomial time, proving P = NP.
S3 is TRUE.
Step 4: Analyze S4:
P2 in P and P2 <=_p P1 is always true for any problem in P. It tells us nothing about whether P1 is in P.
S4 is FALSE.
Final Conclusion: Statements S1 and S3 are TRUE; S2 and S4 are FALSE.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Best visual explanations of algorithm design and complexity analysis.
Exam-focused with GATE PYQ numericals on every major algorithm.