NP-Hard vs NP-Completeness

Aspect	NP-Hard	NP-Complete
Definition	Problem $H$ is NP-hard if every $L\in$ NP reduces to $H$ in polytime: $\forall L\in$ NP, $L\le_p H$. No requirement that $H\in$ NP.	$C$ is NP-complete iff $C$ is both NP-hard and $C\in$ NP. So NP-C = NP ∩ NP-hard.
Verifiable?	Not necessarily verifiable in polytime; may be harder than NP (e.g., Halting, undecidable problems are NP-hard).	Yes, must be verifiable in polytime (certificate check $O(n^k)$).
Examples	Halting Problem, 3-SAT optimization version, TSP optimization; also any NP-complete problem is NP-hard.	Decision versions: SAT, 3-SAT, Clique decision, Vertex Cover decision, Hamiltonian Cycle, Subset Sum decision, TSP decision (is there tour ≤K?).
Reduction direction	To prove NP-hard: reduce known NP-hard/NP-complete $L_0 \le_p H$.	To prove NP-complete: prove (1) $C\in$ NP and (2) $C$ NP-hard (reduce known NP-complete to $C$).
Solvability	If NP-hard problem in P → P=NP, but converse not. NP-hard outside NP cannot be in NP regardless of P vs NP.	If any NP-complete in P → P=NP → all NP problems polytime.
Optimization vs Decision	Optimization forms often NP-hard but not NP-complete because verification of optimality not polytime (just decision version is NP-complete).	Decision versions with yes/no and polytime verifier.

Venn: $P \subseteq$ NP, NP-Complete ⊂ NP, NP-Hard superset overlapping NP (contains NP-C) and extending outside.

Consequence: Showing new problem NP-complete establishes it is among hardest in NP; showing NP-hard shows at least as hard as NP-complete, possibly harder/undecidable.