tag:blogger.com,1999:blog-3722233.post110798885816830031..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Maybe He Missed Some MathLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-1109458790277319592005-02-26T17:59:00.000-05:002005-02-26T17:59:00.000-05:00Thanks Scott, interesting articleThanks Scott, interesting articleYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108226542640610592005-02-12T11:42:00.000-05:002005-02-12T11:42:00.000-05:00From what I could tell, the rest of the book is a ...From what I could tell, the rest of the book is a pretty comprehensible - but a very, <I>very</I> brief- review of most of the mathematics one might need for a grad school. It cannot serve as a textbook of any sort - rather as a coarse intro. For me the chapter on P vs NP (for all its mistakes) actually worked: I was so surprised to learn that there is a possibility that P vs NP is independent, that I Googled it right away and the first result was, naturally, Scott's paper - great reading!<br />PeterAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108188793363454422005-02-12T01:13:00.000-05:002005-02-12T01:13:00.000-05:00This comment has been removed by a blog administrator.Scotthttps://www.blogger.com/profile/09428022255536654006noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108188754142790522005-02-12T01:12:00.000-05:002005-02-12T01:12:00.000-05:00Yaroslav: since I don't think I said this explicit...Yaroslav: since I don't think I said this explicitly in the survey, it means that either P!=NP but there's no proof in the given axiom system, or that there's a polynomial-time algorithm for SAT but no proof of its correctness.Scotthttps://www.blogger.com/profile/09428022255536654006noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108047332368234852005-02-10T09:55:00.000-05:002005-02-10T09:55:00.000-05:00How is the rest of the book? Is it worth recommend...How is the rest of the book? Is it worth recommending?<br /><br />(Perhaps you should drop the author a line, so it could at least appear in errata.)Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108002727235010002005-02-09T21:32:00.000-05:002005-02-09T21:32:00.000-05:00Not such a naive question and no short answer. Che...Not such a naive question and no short answer. Check out this <A HREF="http://www.blogger.com/r?http%3A%2F%2Ftheorie.informatik.uni-ulm.de%2FPersonen%2Ftoran%2Fbeatcs%2Fcolumn81.pdf">survey</A> by Aaronson.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108001611451875222005-02-09T21:13:00.000-05:002005-02-09T21:13:00.000-05:00Perhaps a naive question -- if P=NP is shown to be...Perhaps a naive question -- if P=NP is shown to be independent of other axioms, what does that say about our ability to solve an NP-complete problem in polynomial time?Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1107995723892254152005-02-09T19:35:00.000-05:002005-02-09T19:35:00.000-05:00(From Garey and Johnson so you probably know this....(From Garey and Johnson so you probably know this.)<br />One proposed name for NP was PET.<br />For NOW it stands for Probably exponetial time<br />if P\ne NP then it stands for Provably exponential time<br />(unless NP is n^{log n} or something like that)<br />if P=Np then its Previously exponential time.<br /><br />As for people thinking that P vs NP is ind of stuff,<br />in a survey I did a while back (its in SIGACT NEWS)<br />of 100 theorists only 3 thought it was independent.<br />And one of them emailed me later that he didn't really<br />think that, but thought it would be a cool way to vote.<br />So Garrity is PROVABLY wrongGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.com