tag:blogger.com,1999:blog-3722233.post109829537284676012..comments2023-02-07T18:07:48.632-06:00Comments on Computational Complexity: Conversations with BillLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1098417387515436862004-10-21T22:56:00.000-05:002004-10-21T22:56:00.000-05:00Maybe Bill stopped calling people idiots because h...Maybe Bill stopped calling people idiots because he jumped on the theory bandwagon and became "too nice?"<br /><br />bAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098384007042507252004-10-21T13:40:00.000-05:002004-10-21T13:40:00.000-05:00sorry, I have lost a part of a sentence
I meant re...sorry, I have lost a part of a sentence<br />I meant reals with addintion and linear order (by Berman)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098383767075342682004-10-21T13:36:00.000-05:002004-10-21T13:36:00.000-05:00Naturality of the problem is like a LOGSPACE reduc...Naturality of the problem is like a LOGSPACE reduction.<br />1 there must be a short and easily understandable description of the problem in the terms tought in basic computer science/discrete mathematics course <br />2 the problem description must be short<br />For example, a tiling problem is natural. Everybody knows about tiles, squares, and can understand that this one is a good palcement of tiles and this one is bad. <br />REgexp with squaring seems to be good, but not SO natural because of squaring which is quite 'unnatural'. It is too different from other operators.<br />For example, unsatisfiability of FOL (clearly known by every undergraduate) over reals is also "natural"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098357546773677842004-10-21T06:19:00.000-05:002004-10-21T06:19:00.000-05:00Does MOM also have trouble understanding the trave...Does MOM also have trouble understanding the traveling salesman problem? Maybe it's easier to think abstractly about *a* set of cities than *the* (?) set of states. Though you might want to call it "traveling salesperson."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098346028344392862004-10-21T03:07:00.000-05:002004-10-21T03:07:00.000-05:00Are "proofs" in CompSci as rigorous as those in Ma...Are "proofs" in CompSci as rigorous as those in Mathematics?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098340815293591452004-10-21T01:40:00.000-05:002004-10-21T01:40:00.000-05:00Wow! This is the first conversation I've read abo...Wow! This is the first conversation I've read about, heard about, or heard, where Bill did not call someone an idiot (or worse).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098313215879525832004-10-20T18:00:00.000-05:002004-10-20T18:00:00.000-05:00Wow, these are the only conversations with Bill I ...Wow, these are the only conversations with Bill I have experienced or heard about where Bill didn't call someone an idiot.Anonymousnoreply@blogger.com