Hacker News Reader

Comment by calhoun137 | Hacker News Reader

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.

View on HN

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... 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.

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

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.

Vinay Deolalikar.

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.

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.

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.

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.

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.

Reply on news.ycombinator.com