Hacker News Reader

Comment by Grue3 | Hacker News Reader

Ok, but how long did it take to find a polynomial algorithm for primality checking (published in 2002)? [1] And NP-complete problems are even harder than that! The history of mathematics is rife with conjectures that would be considered true if viewed "scientifically", but have an extremely large counterexample that disproves the whole thing. [2]

[1] https://en.wikipedia.org/wiki/AKS_primality_test [2] https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture

View on HN

Nothing comes close to P=NP. Again and again, across thousands of problems, almost everything ends up being P or NP-hard, and never both.

It is certainly possible that P=NP, but it will involve basically starting most of the last 30 years of theoretical computer science again.

I love the “electric fence” examples, but I’m not as skeptical as Scott that perhaps humans simply haven’t invented the mathematical tools required to break this fence. Isn’t that something that has happened plenty of times?

You could pretty easily write a parody of this article focused on taking square roots of negative numbers. For generations it looked obvious that no matter which number we tried to square, it would never result in a negative number. You can see the same sort of electric fence that can’t just be a coincidence: we can find the square root of zero, but even the slightest bit less than zero and suddenly there is no square root!

Obviously this sounds silly, because we know that mathemticians invented a new tool: imaginary numbers (a name apparently given mockingly by critical mathematicians), which can be used not only to find square roots of negative numbers, but also to solve problems that don’t obviously involve square roots of negative numbers.

It sounds silly because the analogy is a bit silly. Mathematicians didn't spend centuries trying and failing to take square roots of negative numbers, endlessly studying this as some sort of important question or goal. Complex numbers popped up fairly quickly after the serious study of the roots of polynomials began. They're intrinsic to it.

https://en.wikipedia.org/wiki/Complex_number#History

P≠NP is not like that.

It was something like 1500 years between the discovery of squareroot 2 and squareroot -1.

If you view mathematics as the exploration of progressively stranger objects, that there's such a gap between discovering two roots should make us cautious of discounting things after a 100 year search.

We don't know what we don't know.

> It was something like 1500 years between the discovery of squareroot 2 and squareroot -1.

It was something like 200 years between the discovery of sqrt(-1) and more-or-less universal acceptance of -1 as a number in the first place (yes, imaginary numbers predate the universal acceptance of negative numbers). European mathematics in particular favored geometric interpretation of numbers over algebraic interpretations until relatively recently, and while irrational numbers come about very easily in geometry, negative numbers don't have an immediately obvious interpretation, particularly if you exclude it is a convention of directionality.

The irrationality of the square root of 2 was known long (longer than 1500 years) before the invention of complex numbers, never mind root 2 itself. But whatever the duration, there wasn't relatively uninterrupted, continuous study of mathematics over it - that's a fairly recent thing. Mathematical (and other) knowledge was routinely lost or not seriously pursued at all. This supposed 'gap' between two fairly arbitrary discoveries doesn't inform our understanding of the development of mathematics itself as much as you seem to think.

The analogy is not meant to be applied further than “sometimes we invent new mathematical tools solve problems that were impossible to solve previously.”

Yes, and my point is 'it's not a good analogy (nor analogue) for the thing being discussed'. The nature of the things being compared is too dissimilar. Here's a trivial counter-analogy - angle trisection with compass and straightedge. Known since antiquity, proved impossible by Pierre Wantzel, a piddly 180 years ago (with the requisite invention of new mathematical tools).

Introducing imaginary numbers doesn’t make it untrue that negative numbers don’t have a square root in the reals. Your analogy is more akin to maybe physicists will find something that can do nondeterministic computation in polynomial time—interesting in its own right but irrelevant to the mathematical problem as stated.

Of course not. The new tool doesn’t change what is true, but it certainly let us prove things that we couldn’t possibly prove without the tool.

But this is another area where if P=NP you might expect hints to leak through. As Aaronson points out elsewhere, there's a number of problems where people had found practically efficient algorithms, or polynomial-time randomized algorithms, or something, long before they found an actual polynomial-time worst case algorithm. (In addition to primality, linear programming is another example.) For NP-complete problems there's none of that, no such hints leaking through.

We had plenty of evidence that a deterministic primality testing algorithm exists, though. The Miller-Rabin test was known to be randomized polynomial time since the 70s, and assuming the generalized Riemann hypothesis it can be made deterministic polynomial.

And while there was some nuemerical evidence that the Polya conjecture was false, there really wasnt all that much evidence that the conjecture was false. The first counterexample is around 9 billion-- you could find it yourself if you wanted.

> Ok, but how long did it take to find a polynomial algorithm for primality checking

Proving P=NP doesn't require finding a polynomial time algorithm to solve NP-complete problems. Finding such an algorithm is a much greater challenge than proving that one can exist.

Reply on news.ycombinator.com