tag:blogger.com,1999:blog-6555947.post2781186858476147601..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: P vs NP seminarSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6555947.post-47754434472128671522009-04-12T13:16:00.000-06:002009-04-12T13:16:00.000-06:00I see. so proof complexity is really about the NP ...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 ?Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-4016566019392159802009-04-12T12:00:00.000-06:002009-04-12T12:00:00.000-06:00For Proof Complexity, there is this recent technic...For Proof Complexity, there is this recent technical survey, by N. Segerlind: <BR/> <A>http://web.cecs.pdx.edu/~nsegerli/publications/bsl.pdf</A><BR/><BR/>which is a continuation of an older survey of A. Urquhart:<BR/><A>http://www.math.ucla.edu/~asl/bsl/0104/0104-003.ps</A><BR/><BR/>For a non-technical survey, there's an 98 article by Beame and Pitassi:<BR/><A>http://www.cs.toronto.edu/~toni/Papers/survey.ps</A><BR/><BR/>There are other surveys (by Sam Buss - available on the web) and monographs (by jan Krajicek; 1995) on the field.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-67996602245399206342009-04-11T06:25:00.000-06:002009-04-11T06:25:00.000-06:00Well, there is the field of proof complexity. Sho...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).<BR/><BR/>But I'm not too familiar with the area, so I can't cite a survey.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69852948650417142312009-04-10T15:51:00.000-06:002009-04-10T15:51:00.000-06:00Shiva: thanks, I just grabbed the book and it look...Shiva: thanks, I just grabbed the book and it looks great. <BR/><BR/>Paul: 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 ? <BR/><BR/>I am not aware of other classes of methods that break on P = NP.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-572881042994606852009-04-10T15:11:00.000-06:002009-04-10T15:11:00.000-06:00You've mentioned only the stumbling blocks to prov...You'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 . <BR/><BR/>For 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.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-43386338867766826872009-04-10T14:35:00.000-06:002009-04-10T14:35:00.000-06:00There is an excellent book Computational Complexit...There is an excellent book <A HREF="http://www.amazon.com/Computational-Complexity-Theory-Park-Mathematics/dp/082182872X" REL="nofollow">Computational Complexity Theory (Ias/Park City Mathematics Series)</A> written by various experts in the field. You might want to look at week-one of this book.Shiva Kintalihttp://www.blogger.com/profile/07853545928906483737noreply@blogger.com