Complete Problems

Does any/all/some of these complexity classes have hardest problems?

A language $L$ is complete(With respect to some property $Q$) for a complexity(Inituitive hardest) class $C$. For a complexity class $C$ if:

1. $L\in C$
2. $\forall x \in C$, $x\leq L$. The reduction program should have property $Q$.

$\mathsf{ODD} = \{x\mid x\textrm{ is an odd number}\}$. Is it complete? Satisfy the first requirement, but not the second. If you can solve Hamilton cycle efficiently, then you can factor numbers efficiently.

$Q$ should be as weak as possible.

Cook 1972: $\mathsf{SAT}=\{\Phi\mid\textrm{Boolean formula }\Phi\textrm{ is satisfiable}\}$ is complete for $\mathbf{NP}$.

Karp 1973: 22 more Natural $\mathbf{NP}$-complete problems

Both got Turing Awards. Not because their proofs are hard, but their ideas are insightful.