Hacker News new | past | comments | ask | show | jobs | submit login
"Is P Versus NP Formally Independent?" (2003) (scottaaronson.com)
4 points by hc on Jan 26, 2009 | hide | past | favorite | 1 comment



This 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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: