A theorem showing that two complexity classes are distinct. Most separation theorems have been proved by diagonalization.