Low ●

🧮 P, NP & NP-Completeness

Why it matters: Usually one conceptual question: which statements about P, NP, NP-hard and NP-complete are true.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 3 done.

Formulas

Inclusions
P ⊆ NP; NP-complete = NP ∩ NP-hard; if P ≠ NP, then P ∩ NP-complete = ∅
Reduction direction
A ≤ₚ B and B ∈ P ⇒ A ∈ P; A NP-hard and A ≤ₚ B ⇒ B NP-hard
Classic chain
SAT → 3-SAT → Clique ↔ Independent set ↔ Vertex cover; Hamiltonian cycle → TSP
Pairs that differ
2-SAT ∈ P vs 3-SAT NPC; Euler circuit ∈ P vs Hamiltonian NPC; shortest vs longest simple path

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Which statements about P / NP / NP-complete are true
Inclusion relations and consequences of P = NP; NP-hard problems that are not in NP.
★★★
Reduction direction
If problem A reduces to B, what do you learn about A or B?
★★★
Known NP-complete or polynomial problems
Pick the NP-complete problem from a list (2-SAT, Hamiltonian cycle, shortest path, MST).

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Common traps

NP stands for non-deterministic polynomial, not "not polynomial".
NP-hard problems need not be in NP (the halting problem is NP-hard).
To show B is hard you reduce a known hard problem to B, not B to it.
"Easy to verify" does not mean "easy to solve".