4 ms·

According to this article, he claims to have found a strong solution. My prediction was/is that the types of solutions asked for by the millennium problem were

According to this article, he claims to have found a strong solution. My prediction was/is that the types of solutions asked for by the millennium problem were not going to exist, so my first instinct is to not believe this, but clearly that is not a good reason. So, at the risk of being wrong, I will make the following not so bold prediction: there is a critical mistake somewhere in the paper and the approach will ultimately not pan out.

ckozlowski 13y ago
There was a researcher from HP that did the same for "NP Hard" some years ago, that finished in the same place. He took a new angle, but ultimately, the proof didn't hold up. While it was disappointing in the end, the attempts are laudable. Here's hoping he got it, and if he didn't, that he at least manages to contribute a novel approach.
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 ago
  Precisely. 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 ago
    It 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 ago
    Vinay Deolalikar.
  - umanwizard 13y ago
    Why 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 ago
  That'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 ago
    I'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 ago
      Funny 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.

ckozlowski 13y ago

There was a researcher from HP that did the same for "NP Hard" some years ago, that finished in the same place. He took a new angle, but ultimately, the proof didn't hold up. While it was disappointing in the end, the attempts are laudable. Here's hoping he got it, and if he didn't, that he at least manages to contribute a novel approach.

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 ago
Precisely. 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 ago
  It 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 ago
  Vinay Deolalikar.
- umanwizard 13y ago
  Why 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 ago
That'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 ago
  I'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 ago
    Funny 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.