tag:blogger.com,1999:blog-3722233.post110798885816830031..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Maybe He Missed Some MathLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1109458790277319592005-02-26T16:59:00.000-06:002005-02-26T16:59:00.000-06:00Thanks Scott, interesting articleThanks Scott, interesting articleYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108226542640610592005-02-12T10:42:00.000-06:002005-02-12T10:42:00.000-06: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-1108047332368234852005-02-10T08:55:00.000-06:002005-02-10T08:55:00.000-06: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-09T20:32:00.000-06:002005-02-09T20:32:00.000-06: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.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1108001611451875222005-02-09T20:13:00.000-06:002005-02-09T20:13:00.000-06: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-09T18:35:00.000-06:002005-02-09T18:35:00.000-06: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