Hacker News Reader

Comment by bla3 | Hacker News Reader

> "Proof by contradiction. Assume P=NP. Let y be a proof that P=NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P=NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."

Love this :)

View on HN

Sorry. Too many experiences to really buy the logic "it can be done, it has not been done, hence contradiction". Indeed e.g. the proof of Fermat's theorem (Wikipedia: After 358 years of effort by mathematicians, the first successful proof was released in 1994 by Andrew Wiles, and formally published in 1995; it was described as a "stunning advance" in the citation for Wiles's Abel Prize award in 2016.) would be a contradiction of that logic. (Indeed, I am very confident that mathematics is a much more developed a mature field then IT).

The only time such an argument had been yielded and has some value is in my (not so, I guess) humble opinion when I think Fermi used the argument that if there was a lower energy level of water there surely would have been an animal by now that used this extra energy by converting water to this state (although I cannot find a link to this quite so quickly, so perhaps the argument was slightly different).

It's a joke, not a proof. I thought it was funny.

I'm very confident that orders of magnitude more man-hours have been spent thinking about P=NP in the past 20 years than were spent in the whole 358 years on Fermat's theorem. The number of people in academic situations to work on hard problems has increased exponentially.

I think it's fair to assume that there are potentially asymptotic limits to what can be achieved, but it's not that we default to one conclusion or the other, but that we conclude that whatever might be the real solution, the complexity of the proof is insurmountable or doesn't exist.

First off, it's a joke explanation and not meant to be taken seriously anyways.

But more notably, like Fermat's theorem, we can probably conclude that there's no easy quadratic or cubic algorithm for SAT that we've somehow missed. If P = NP, then, the most likely algorithm we'd see would be some hideous combinatorial algorithm that has a constant factor of 3^2^2^4 lurking in it that is completely impractical.

But it makes no sense.

P doesn't mean fast, it means polynomial.

A runtime of O(n + a) is polynomial (and just O(n)!), but with a big enough "a" (e.g. 2^999999999999999999999999999999999) it's likely large enough to be practically non-commutable.

I.e. there are "practically non-commutable" polynomial algorithm.

So the idea "there is not proof because we should have found it else wise" is deeply flawed.

Of course it makes no sense, it's a joke.

FWIW, it hardly matters, as the antecedent--the existence of a competent computer scientist--is unlikely at best.

Can't lose with that argument, eh? :)

Reply on news.ycombinator.com