Why is it so hard to prove P != NP, or even to prove
super-linear circuit lower bounds? While we often blame a lack of
combinatorial ingenuity, the bottleneck might be more fundamental:
the logical strength of our mathematical tools.
Hilbert, motivating his list of 23 problems, mentions the
arithmetical formulation of the concept of the continuum in the
works of Cauchy, Bolzano and Cantor, and the discovery of
non-Euclidean geometry by Gauss, Bolyai and Lobachevsky, as...
