# What are the prerequisites in order to pursue the P vs. NP problem?

I'm a math major at Berkeley, and am focusing or logics/fundamentals, in particulars groups. I was just trying to see if I were to, for personal interest, get a better understand and perhaps try pursuing the p np problem, what sort of courses (or background since different institutions' courses carry different focus) do I need?

Thank You!

-
In general I think it is a very bad idea to structure your education around the pursuit of a particular problem. See Terence Tao's thoughts on the matter here (the rest of his advice is also well worth reading): terrytao.wordpress.com/career-advice/… – Qiaochu Yuan May 5 '12 at 17:59
I would suggest browsing Scott Aaronson's blog and looking at the P vs. NP poll. The latter is a list of highly-informed opinions, representing in a sense our current knowledge, which may therefore help you picking a relevant field to study, build a project, or more likely and mercifully make you feel that the problem is already well taken care of. Anyway, we all know P$\neq$NP. To better understand the implications though, you may go to complexity theory courses, or read mathoverflow, and blogs, which contain alot of crucial folklore insights -in particular R.J. Lipton's, in comments. – plm May 5 '12 at 18:25
I find win.tue.nl/~gwoegi/P-versus-NP.htm interesting, because it contains roughly the same number of references to proofs that P=NP (currently 44) than to proofs of the opposite. You can also find the first version of Vinay Deolalikar's much discussed paper there. A totally different approach was pursued by math.berkeley.edu/~rhodes, but it seems to lack enough connections to (pseudo) randomness for being successful. – Thomas Klimpel May 5 '12 at 23:14

Note that we don't have even much weaker results, e.g. we cannot show that SAT is not solvable in quadratic time (i.e. $SAT \notin \mathsf{DTime}(n^2)$), or by circuits of constant depth composed of AND, OR, NOT, MOD gates (i.e. show that $SAT \notin \mathsf{ACC^0}$). Even proving these kind of results would be considered a major break through in complexity theory.