tag:blogger.com,1999:blog-3722233.post114484400447092937..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: GĂ¶del PrizeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-80000159907530549632007-06-26T14:39:00.000-05:002007-06-26T14:39:00.000-05:00Unfortunately, solving "Primes in P" does not solv...Unfortunately, solving "Primes in P" does not solve the factorization algorithm. They are two totally different problems. So while you may try up to N^0.5 numbers to find a factor, (NP, given that it grows by factor of 10 every time you add two digits), figuring out if one trial number is prime or not could be determined in polynomial time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145159968330939822006-04-15T22:59:00.000-05:002006-04-15T22:59:00.000-05:00Anonymous guy #1: The fact is that there are thous...Anonymous guy #1: <I>The fact is that there are <B>thousands of NP-hard problems</B> from dozens of research fields, all of which were either explicitly or implicitly being studied for efficient algorithms by many researchers over many years. It is the fact that these are all actually the same problem that gives support to the belief .<BR/>Thu Apr 13, 11:13:38 AM CDT<BR/></I><BR/><BR/>Anonymous guy #2:<I>This does not give any support for the conjecture P!=NP. All these <B>thousands of NP-complete problems</B> may require the same novel, still to be discovered algorithmic technique.<BR/>Thu Apr 13, 01:24:34 PM CDT</I><BR/><BR/>I hate to be pedantic, but:<BR/><BR/>1) Anonymous guy 1 said <B>NP-hard</B>, not NP-complete. All NP-complete problems are NP-hard, but not vice versa. Informally, a problem is NP-hard if all problems in NP are reducible to it in polynomial time. NP-complete is the set of problems that are in NP and are also NP-hard. For example, the halting problem is NP-hard, but not NP-complete. <BR/><BR/>2) "All these thousands of NP-complete problems <B>may</B> require the same novel, still to be discovered algorithmic technique." <BR/>All NP-complete problems are reducible to each other, by definition. If you can solve one, you can solve them all. So that comment is a little redundant. <BR/><BR/>Anonymous guy #1's point is that the fact that many researchers from many fields, working independently, have been unable to come up with efficient solutions to these problems, even though they had no idea they were all working on essentially the same problem. It is not evidence, but it strongly suggests that P is probably not equal to NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144952674302000652006-04-13T13:24:00.000-05:002006-04-13T13:24:00.000-05:00This does not give any support for the conjecture ...This does not give any support for the conjecture P!=NP. All these thousands of NP-complete problems may require the same novel, still to be discovered algorithmic technique.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144944818518459522006-04-13T11:13:00.000-05:002006-04-13T11:13:00.000-05:00If it were only one problem in one area of researc...If it were only one problem in one area of research like factoring or satisfiability then the support for the belief that P!=NP would be a lot weaker than it is. The fact is that there are thousands of NP-hard problems from dozens of research fields, all of which were either explicitly or implicitly being studied for efficient algorithms by many researchers over many years. It is the fact that these are all actually the same problem that gives support to the belief .Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144942827419920402006-04-13T10:40:00.000-05:002006-04-13T10:40:00.000-05:00Uh... I eagerly await your rigorous proof that eff...<I>Uh... I eagerly await your rigorous proof that efficiently checking all n-bit strings (an exponential number) for the property "String x satisfies circuit C" is "clearly impossible"... but I can't say I'm holding my breath...</I><BR/><BR/>I'm pretty sure the point was that there is no reason to believe that one can't find satisfying assignments to circuits in some way other than searching through all of them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144935943981359732006-04-13T08:45:00.000-05:002006-04-13T08:45:00.000-05:00Of course, this is patently false. It is not just ...<I>Of course, this is patently false. It is not just "counterintuitive," it is clearly impossible, and it has little to nothing to do with P vs. NP.</I><BR/><BR/>Uh... I eagerly await your rigorous proof that efficiently checking all n-bit strings (an exponential number) for the property "String x satisfies circuit C" is "clearly impossible"... but I can't say I'm holding my breath...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144892256872556582006-04-12T20:37:00.000-05:002006-04-12T20:37:00.000-05:00No. People believe P != NP because it seems very c...<I>No. People believe P != NP because it seems very counterintuitive to say that we can check an exponential number of elements for some property in time comparable to checking just one of them.</I><BR/><BR/>Of course, this is patently false. It is not just "counterintuitive," it is clearly impossible, and it has little to nothing to do with P vs. NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144888460802536432006-04-12T19:34:00.000-05:002006-04-12T19:34:00.000-05:00P != NP is just a religious belief.No. People beli...<I>P != NP is just a religious belief.</I><BR/><BR/>No. People believe P != NP because it seems very counterintuitive to say that we can check an exponential number of elements for some property in time comparable to checking just one of them.<BR/><BR/>Obviously that's not a proof, but it is an intuitive justification for the conjecture. But of course many "counterintuitive" things have, in the past, turned out to be true anyway, so there is no call to be closed-minded about your personal hunch that P != NP -- but that isn't the same as saying that belief in the conjecture is groundless or egomaniacal.<BR/><BR/>Now hardness of factoring, on the other hand, has no such intuitive justification, and if you say "hardness of factoring is just a religious belief" I'd be more inclined to agree with you...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144884279445607342006-04-12T18:24:00.000-05:002006-04-12T18:24:00.000-05:00Is there a reason why most researchers believe thi...<B>Is there a reason why most researchers believe this? I've never heard a good argument beyond something like "it would have some weird consequences." <BR/></B><BR/><BR/>They "believe" so because they want to believe so.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144881746308887752006-04-12T17:42:00.000-05:002006-04-12T17:42:00.000-05:00P != NP is just a religious belief.If not a blatan...<I>P != NP is just a religious belief.</I><BR/><BR/>If not a blatant symptom of egomania.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144877551362266952006-04-12T16:32:00.000-05:002006-04-12T16:32:00.000-05:00P != NP is just a religious belief.P != NP is just a religious belief.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144875290129649832006-04-12T15:54:00.000-05:002006-04-12T15:54:00.000-05:00Anyway, most researchers believe P != NPIs there a...<I>Anyway, most researchers believe P != NP</I><BR/><BR/>Is there a reason why most researchers believe this? I've never heard a good argument beyond something like "it would have some weird consequences."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144857487072828962006-04-12T10:58:00.000-05:002006-04-12T10:58:00.000-05:00i thought this was announced a while back. i guess...i thought this was announced a while back. i guess the IITK grapevine is more effective ;)<BR/><BR/>http://geomblog.blogspot.com/2006/03/2006-gdel-prize.htmlSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144853201555648922006-04-12T09:46:00.000-05:002006-04-12T09:46:00.000-05:00To try to get a handle on the distance between PRI...To try to get a handle on the distance between PRIMES and NP-complete problems:<BR/><BR/>before Agrawal, were there P-time algorithms to recognize any infinite subset of the prime numbers? I've never seen such a result. <BR/><BR/>Since we don't (or didn't) have simple special cases to work with (true, we have simple subsets of COMPOSITES), it's hard to see the building blocks of a reduction. P-completeness looks equally unlikely.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144852113257853552006-04-12T09:28:00.000-05:002006-04-12T09:28:00.000-05:00Cool. My guess is that Kayal and Saxena may be the...Cool. My guess is that Kayal and Saxena may be the youngest winners so far of the Godel prize.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144851169991050342006-04-12T09:12:00.000-05:002006-04-12T09:12:00.000-05:00>Even proving that it couldn't be>done would solve...>Even proving that it couldn't be<BR/>>done would solve the P/NP puzzle. <BR/><BR/>Would? I thought if someone prove it can't be done, he/she have just proven it can't be done, saying nothing about all the other approches.Osiashttps://www.blogger.com/profile/18342583333092991594noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144850152432281812006-04-12T08:55:00.000-05:002006-04-12T08:55:00.000-05:00Osias, I'm sure there have been a hundred "attempt...Osias, I'm sure there have been a hundred "attempts" at doing so. And even long before the Primes in P result, because of the probabilistic algorithms for primality testing.<BR/><BR/>Anyway, most researchers believe P != NP so they probably wouldn't spend too much time on that after the first several tricks did't work. Even proving that it couldn't be done would solve the P/NP puzzle.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144845229808105942006-04-12T07:33:00.000-05:002006-04-12T07:33:00.000-05:00Isn't there any attempts to encode a SAT instance ...Isn't there any attempts to encode a SAT instance as a big number, such it's satisfiable only if it's composite.. or something like that? Or is this idea too silly?Osiashttps://www.blogger.com/profile/18342583333092991594noreply@blogger.com