My favourite results are the existence of NP-complete problems (Cook), the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle, and Faggin's characterization of NP in terms of second order logic.
Stefan Geschke
- 16.2k
- 2
- 54
- 82