I'm thinking of topics to discuss over the summer with students here, and decided on introducing people to complexity theory via the question, "Why haven't we solved the P vs NP problem?". The title is a little tongue-in-cheek: the real idea is to use P vs NP to explore some concepts in complexity theory, for an audience that has no real familiarity with the topic.
Thus far, I'm working off the "diagonalization-oracles-boolean-circuits-razborov-rudich" story line, with an addition at the end for algebraization, and P vs NC. But since this isn't my real area of expertise, I'm throwing out a request for suggestions: what topics am I missing when discussing the various attacks on P vs NP ?
p.s I'm using Scott Aaronson's P vs NP survey as a rough starting guide for references.
There is an excellent book Computational Complexity Theory (Ias/Park City Mathematics Series) written by various experts in the field. You might want to look at week-one of this book.
ReplyDeleteYou've mentioned only the stumbling blocks to proving P != NP. You could also show why classes of attempts to prove P=NP are bound to fail, though this might be too different from the former .
ReplyDeleteFor example, there is the line of work showing that classes of lifted LPs and SDPs won't work, starting with the paper of Yannakakis in STOC 1988, which was in response to a hard-to-refute claim of an LP for TSP due to Swart in the early 1980's. I am not sure of a good summary for this line of work, though.
Shiva: thanks, I just grabbed the book and it looks great.
ReplyDeletePaul: I definitely want to cover the Yannakakis result if I can. I'm not aware of the work that followed it: is there something you can point me to for the LP blocks ?
I am not aware of other classes of methods that break on P = NP.
Well, there is the field of proof complexity. Showing superpolynomial lower bounds on the size of a proof in a certain formalization should correspond to lower bounds on classes of algorithms (e.g. trying to solve SAT by resolution only or by branching only).
ReplyDeleteBut I'm not too familiar with the area, so I can't cite a survey.
For Proof Complexity, there is this recent technical survey, by N. Segerlind:
ReplyDeletehttp://web.cecs.pdx.edu/~nsegerli/publications/bsl.pdf
which is a continuation of an older survey of A. Urquhart:
http://www.math.ucla.edu/~asl/bsl/0104/0104-003.ps
For a non-technical survey, there's an 98 article by Beame and Pitassi:
http://www.cs.toronto.edu/~toni/Papers/survey.ps
There are other surveys (by Sam Buss - available on the web) and monographs (by jan Krajicek; 1995) on the field.
I see. so proof complexity is really about the NP vs coNP problem, isn't it ? It's a great topic to cover, and I'd like to do it (the references provided are excellent, thanks!). However, I'm still trying to think about Paul's question: are there known attacks on P = NP ?
ReplyDelete