4 ms·
The prize is awarded either way. You have to prove that a solution exists or doesn't exist. http://www.claymath.org/millennium-problems/rules-millennium-prizes
by sp332 13y ago
The prize is awarded either way. You have to prove that a solution exists or doesn't exist. http://www.claymath.org/millennium-problems/rules-millennium-prizes http://www.claymath.org/millennium-problems/rules-millennium... In the case of the P versus NP problem and the Navier-Stokes problem, the SAB will consider the award of the Millennium Prize for deciding the question in either direction.
- ckozlowski 13y agoPrecisely. In the case of the NP-hard example I presented below, the researcher (who's name eludes me) attempted to prove that a solution did not exist. From a computer science perspective, this would be favorable, as a solution for NP-hard would render a lot of crypto useless overnight. =P
- Genmutant 13y agoIt wouldn't (probably) render the algorithms who rest upon the assumption that P!=NP useless. You still have to find a fast algorithm for the problem. Just because it is in P doesn't mean there exists a (practical) fast algorithm to break the crypto.
- psuter 13y agoVinay Deolalikar.
- umanwizard 13y agoWhy do people keep repeating this notion? P doesn't mean fast or even tractable within the expected lifetime of the universe. "Polynomial time algorithms are fast" is an extremely vague statement for intuition, and not actually true except if you define carefully what you mean (that is, that they are faster as n->+inf...) If crypto relies on some algorithms that are O(n^100000000000) where n is key length, I'm not very worried.
- Someone 13y agoThat's true, but if the paper turns out to have an essential flaw, it does not prove that no solution exists, it just does not prove that a solution exists, just like this post. I think it would be funny if someone really went just that far, though: give an existence proof for a solution that is not constructive.
- calhoun137 13y agoI'm curious why you think that would be funny, since in my opinion, that is the most likely outcome should such a solution exist at all.
- Someone 13y agoFunny probably is not the right word, but I like it when mathematical breakthroughs reinforce the public's perception of mathematicians as living in their minds, not in the world. Because of that, I would find it more 'enjoyable' to see a proof that a polynomial time algorithm for TSP exists, than to see a proof by example, or to see a proof that go is a win for white or chess for black than to see a program that plays the game perfectly (and of course, within the space of constructive proofs, there are gradations. Exhaustive search would be extremely dull; a theory that generalizes to other problem spaces would be more interesting. Moving to another problem the various O(<n^3) matrix multiplication algorithms are 'funny' because, AFAIK, none of them has practical use.