tag:blogger.com,1999:blog-3722233.post9213016457113386470..comments2021-09-20T20:42:50.990-05:00Comments on Computational Complexity: Certifying primality in a CONSTANT number of operationsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-73611387366175691012013-08-02T09:16:38.327-05:002013-08-02T09:16:38.327-05:00Among logicians, the Matiyasevich result was not a...Among logicians, the Matiyasevich result was not a surprise. There were several people working on it at the time, and the existing partial results of Julia Robinson were tantalizingly close. Martin Davis had even gone so far as to predict that some young Russian was going to complete the existing work (his point being that the end was in sight, but horribly tedious).william e embahttp://xxxnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59777536808023953852013-08-01T17:36:05.093-05:002013-08-01T17:36:05.093-05:00Are there really that many researchers working on ...Are there really that many researchers working on the problem?<br /><br />My experience is that excluding GCT almost no-one works on a direct proof or disproof. If you add research towards proving the hypothesis of conditional result that would then give (usually) P <> NP , you'll get probably about 100 researchers or so.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7067259349942238662013-07-31T15:44:09.266-05:002013-07-31T15:44:09.266-05:00Sol to H10 like if P=NP: YES, people thought it ju...Sol to H10 like if P=NP: YES, people thought it just so unlikel.<br /><br />Sol to H10 NOT like P=NP: Not that many people were thinking about it.<br />Was not widely regarded as an important problem.<br /><br />but YES, this is a case where the conventional wisdom was wrong- a lesson for us all.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70312396956988535682013-07-31T08:40:05.994-05:002013-07-31T08:40:05.994-05:00There may be something here to wonder about for co...There may be something here to wonder about for complexity theory. Most people didn't believe that the r.e. sets are diophantine since that would have so many unlikely consequences, as e.g. that the primes are diophantine, none of which were believed to hold, and were far from being proved to hold. In fact, Matiyasevich's result came rather unexpected and was of the P=NP-type of resolving Hilbert's 10-th problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81825786107924699642013-07-30T03:30:28.687-05:002013-07-30T03:30:28.687-05:00I think that before Matiyasevich's result it w...I think that before Matiyasevich's result it was not known that there is a such a polynomial for the primes. So probably the case for the primes is not easier than the case for all r.e. sets.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18928024751735968542013-07-29T14:25:17.114-05:002013-07-29T14:25:17.114-05:00Correct- the numbers a1,...,a13 could be enormous....Correct- the numbers a1,...,a13 could be enormous.<br /><br />So good point- this does NOT give an alternative proof that<br />Primes is in NP.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43525468698005573062013-07-29T12:54:45.325-05:002013-07-29T12:54:45.325-05:00There would be no reason to expect the "witne...There would be no reason to expect the "witness" (a1,...,a13) to have a number of bits that is polynomially related to the number of bits in "x", right?Mikenoreply@blogger.com