7
$\begingroup$

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!

  • 2
    I find http://www.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 http://math.berkeley.edu/~rhodes, but it seems to lack enough connections to (pseudo) randomness for being successful.2012-05-05

1 Answers 1

5

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.