3 ms·
"Is P Versus NP Formally Independent?" (2003)
- michael_nielsen 18y agoThis is a wonderful paper. The Razborov-Rudich theorem, in particular, is a classic result, up with the unsolvability of the halting problem, and Goedel's incompleteness, in my opinion. It's described in section 4 of this paper. The rest is also well worth reading.