I'm quoting the following (landmark) paper:
Theodore Baker, John Gill, and Robert Solovay Relativizations of the P?=NP Question SIAM Journal of Computing, Volume 4, Number 4, December 1975, pages 431-442.
From the first page,"It seems unlikely that ordinary diagonalization are adequate for producing an example of a language in NP but not in P...".
I'm fairly rusty on math, so I was wondering if someone could briefly explain "ordinary" diagonalization and maybe give a few examples. I'd really like to see this in detail, beause I'd like to explore this more. Can they be as simple as I think they can be? I'm hoping to get a better understanding of the (possibly broad) grounds that diagonlization methods cover.