Complexity Classes $P$, $NP$, $NP$-Complete, $NP$-Hard — Definitions & Relations

Definitions

• $P$ (Polynomial): Decision problems solvable by deterministic TM in $O(n^k)$ for some $k$. Example: Sorting, MST, Shortest path (non-neg). Tractably solvable.
• $NP$ (Nondeterministic Polynomial): Problems where yes instances have certificate verifiable in polytime by deterministic TM (equivalently solvable by nondet TM in polytime). $P\subseteq NP$. Example: SAT, Hamiltonian Cycle decision, Subset Sum.
• $NP$-Hard: Problem $H$ such that $\forall L\in NP$, $L\le_p H$ (polytime reducible). No need to be in $NP$; at least as hard as hardest in $NP$. Example: Halting Problem, TSP optimization, any NP-complete problem.
• $NP$-Complete: $NP \cap$ $NP$-Hard = hardest problems in $NP$. Formal: $C\in NP$ and $\forall L\in NP$, $L\le_p C$. Cook proved SAT is NP-complete. Example: 3-SAT, Clique, Vertex Cover decision, Hamiltonian Cycle.

Relations

P ⊆ NP   (unknown if equal — Clay Millennium)
NP-Complete ⊂ NP
NP-Complete ⊂ NP-Hard
NP-Hard extends outside NP (includes undecidable)
P = NP  ⇔  some NP-complete ∈ P  ⇔  all NP-complete ∈ P
If any NP-hard problem outside NP is in P, not relevant (still P vs NP open).

Venn diagram: Large oval NP-Hard; inside it smaller oval NP; within NP: P region and NP-Complete ring (NP-Complete = intersection of NP-Hard with NP). Outside NP-Hard? None — NP-Hard superset.

Consequences: Proving new problem $X$ NP-complete shows it is among hardest in $NP$; proving NP-hard shows at least as hard (possibly harder than NP).