GATE CS - THEORY OF COMPUTATION:Computational Complexity
Mastering computational complexity concepts and implementation.
Computational Complexity for GATE CS
GATE complexity is definitions + relationships: P ⊆ NP, NP-complete, and what a polynomial reduction means. Rarely a full Cook-Levin proof.
Classes
| Class | Idea |
|---|---|
| P | Decidable in poly time on deterministic TM |
| NP | Verifiable in poly time (or decidable in poly time on NTM) |
| NP-hard | Every NP problem ≤p it |
| NP-complete | NP-hard and in NP |
If any NPC problem is in P, then P = NP (open).
Reductions
(A le_p B): poly-time function maps instances of (A) to (B) preserving yes/no. To prove (B) NP-hard, reduce a known NP-hard (A) to (B).
Exam habits
- P ⊆ NP is the standard assumption statement (not "proven equal")
- Sorting is in P; SAT is NPC
- Do not claim "NP means non-polynomial" — that is wrong
Hub: GATE.
Progress