This work is licensed under a
Creative Commons License.
|
Wednesday, April 12, 2006
Gödel Prize
Posted by Lance
The EATCS has announced the winners of the Gödel Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena for their paper Primes in P.I started this weblog shortly after the announcement of the Primes in P result which was the topic of my third post. Now the result has won the award for best recent journal paper. Either that was a very quick process or I have been writing this weblog too long.
7:09 AM
# 18 comments
-
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?
-
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.
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.
-
>Even proving that it couldn't be
>done would solve the P/NP puzzle.
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.
-
Cool. My guess is that Kayal and Saxena may be the youngest winners so far of the Godel prize.
-
To try to get a handle on the distance between PRIMES and NP-complete problems:
before Agrawal, were there P-time algorithms to recognize any infinite subset of the prime numbers? I've never seen such a result.
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.
-
i thought this was announced a while back. i guess the IITK grapevine is more effective ;)
http://geomblog.blogspot.com/2006/03/2006-gdel-prize.html
-
Anyway, most researchers believe P != NP
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."
-
P != NP is just a religious belief.
-
P != NP is just a religious belief.
If not a blatant symptom of egomania.
-
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."
They "believe" so because they want to believe so.
-
P != NP is just a religious belief.
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.
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.
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...
-
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.
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.
-
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.
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...
-
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'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.
-
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 .
-
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.
-
Anonymous guy #1: 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 .
Thu Apr 13, 11:13:38 AM CDT
Anonymous guy #2: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.
Thu Apr 13, 01:24:34 PM CDT
I hate to be pedantic, but:
1) Anonymous guy 1 said NP-hard, 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.
2) "All these thousands of NP-complete problems may require the same novel, still to be discovered algorithmic technique."
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.
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.
-
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.
Links to this post:
Weblog Home
Archives
