$P$, $NP$, $NP$-Hard, $NP$-Complete — Relationship (as in Q22)

Definitions:

• $P$: solvable in polytime deterministic.
• $NP$: verifiable in polytime deterministic (or solvable nondet polytime).
• $NP$-Hard: every $NP$ problem polytime reduces to it ($L\le_p H$ ∀$L$∈$NP$).
• $NP$-Complete: $NP$-Hard ∧ ∈$NP$.

Relations:

• $P \subseteq NP$, unknown equality.
• $NP$-Complete = $NP$ ∩ $NP$-Hard.
• $P = NP$ iff some (equivalently all) $NP$-complete ∈ $P$.
• $NP$-Hard includes undecidable problems outside $NP$ (e.g., Halting) → strictly larger.

Diagram concept: Draw big rectangle of all problems, big oval $NP$-Hard overlapping; inside oval, smaller oval $NP$; inside $NP$, region $P$ and ring $NP$-Complete at hardest edge of $NP$ overlapping $NP$-Hard.

Proving $X$ $NP$-complete: Show $X∈NP$ (certificate verifier) + reduce known $NP$-complete $Y \le_p X$.