Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Barriers to proving P!=NP (scottaaronson.com)
6 points by iamwil on Sept 17, 2007 | hide | past | favorite | 2 comments



I don't get everything being discussed in the powerpoint linked in the article, but it seems like the result is he figured out that none of the current techniques they've been using to make progress on the P != NP problem will work. So that means going back to the drawing board.

http://en.wikipedia.org/wiki/Relativization http://citeseer.ist.psu.edu/fortnow94role.html

Anyone else have enough background in Complexity Theory to enlighten it some more?


It is expected that any claims of a proof for P != NP would explain how they have overcome these barriers in their proof. Otherwise, few would consider looking at the proof carefully.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

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

Search: