tag:blogger.com,1999:blog-3722233.post7982235816200461910..comments2023-01-30T06:53:58.825-06:00Comments on Computational Complexity: Factoring in P ?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-19267708767728726522010-08-24T17:03:11.132-05:002010-08-24T17:03:11.132-05:00Another Fields medalist who cares about P vs. NP i...Another Fields medalist who cares about P vs. NP is Steve Smale. I couldn't say <br />when he started caring about P vs. NP <br />but I would hazard a guess that it was <br />during the 1980s: in 1983 he published <br />a paper on the average-case complexity <br />of the simplex method. I should also <br />point out that he is one of the Ss in <br />the BSS model of computation --- a <br />computational model that <br />provides important analogues of the <br />P vs. NP question.J. Maurice Rojashttp://www.math.tamu.edu/~rojasnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63006401771879625402010-08-13T10:29:16.124-05:002010-08-13T10:29:16.124-05:00Since when to mathematicians care about poly time....Since when to mathematicians care about poly time.? Actually, for a while now.<br />Note that Terry Tao and William Gowers,<br />both Field Medalists, care about these things.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11358950520698187492010-08-12T16:57:35.362-05:002010-08-12T16:57:35.362-05:00WWVDND?
Why in the world do people like you even ...<i>WWVDND?</i><br /><br />Why in the world do people like you even bother to read academic blogs? Is it just to look for chances to be cantankerous?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61179435510737781682010-08-12T07:30:06.803-05:002010-08-12T07:30:06.803-05:00My motto used to be “What would Grisha Perelman Do...My motto used to be “What would Grisha Perelman Do” WWGPD?<br />But now it’s quickly and unexpectedly been supplemented by “What would V. D. NOT Do” WWVDND? or how NOT to solve a milleniyum prize problem!<br />BTW when is the next Update? Can I download it with my next Windows Update? Will I be forced to restart my brain each time after I glance through an updated pdf, like I’m forced to restart my computer after a Windows update?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51481894794014472642010-08-12T04:21:17.144-05:002010-08-12T04:21:17.144-05:00How many scientists from MIT does it take to solve...How many scientists from MIT does it take to solve a millenium prize problem?<br /><br />200,000Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90117004530309814232010-08-12T04:12:01.803-05:002010-08-12T04:12:01.803-05:00How many scientists from MIT does it take to solve...How many scientists from MIT does it take to solve P / NP?<br /><br />How many scientists from MIT does it take change a light bulb?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75965665641929056162010-08-11T15:16:05.209-05:002010-08-11T15:16:05.209-05:00Factoring is easy if you are a mathematician becau...Factoring is easy if you are a mathematician because there is a well-defined, terminating algorithm to factor. Since when do mathematicians care about the notion of polynomial time?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37175434000433926472010-08-11T10:49:32.805-05:002010-08-11T10:49:32.805-05:00Factoring *is* easy from an intuitive point of vie...Factoring *is* easy from an intuitive point of view. Using sieve-like methods to find factors dates back to Eratosthenes, and for small numbers this works great. Not to mention that the prime factorization is unique. <br /><br />What makes factoring hard is the formal notion of complexity and specially the idea of the size of the input. In fact I use factoring as an example in class as an example of why the notion of the size of input vs size of numbers concept is so important. <br /><br />It's almost like the Newtonian vs relativistic view of mechanics. The first view is limited but it took long distances (in our case large numbers) to truly recognize the difference.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86329091726281748422010-08-11T10:18:48.804-05:002010-08-11T10:18:48.804-05:00I imagine they meant "the algorithm to comput...I imagine they meant "the algorithm to compute this is not complicated", which is obviously true. Also, a lot of computations are used in proofs only.Anonymousnoreply@blogger.com