Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
13  
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
2  
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
2  
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

1 Answer 1

up vote 4 down vote accepted

I agree with Qiaochu.

No one really knows what kind of math will be helpful to solve the question. There are several (somewhat) active approaches and each of them is quite a topic in itself: Circuit Lower Bounds, Geometric Complexity Theory, etc.

If you want to understand the problem, I would suggest taking an algorithms course and a complexity theory course. You can also just read a book (e.g. Sipser), there are not much mathematics required to understand the problem. However if you want to obtain a deeper understanding of the problem and why it is a difficult problem then a graduate course in complexity theory would be useful. Also check Arora and Barak's book, the draft is available online.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.