4 ms·

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!

by Grue3 9y ago

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 https://en.wikipedia.org/wiki/AKS_primality_test [2] https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture

CJefferson 9y ago
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.
- baddox 9y ago
  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.
  - pvg 9y ago
    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 https://en.wikipedia.org/wiki/Complex_number#History P≠NP is not like that.
    - SomeStupidPoint 9y ago
      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.
      - jcranmer 9y ago
        > 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.
      - pvg 9y ago
        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.
  - dullcrisp 9y ago
    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.
    - baddox 9y ago
      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.
wtallis 9y ago
> 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.
Sniffnoy 9y ago
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.
zzazzdsa 9y ago
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.

by Grue3 9y ago

CJefferson 9y ago

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.

baddox 9y ago
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.
- pvg 9y ago
  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 https://en.wikipedia.org/wiki/Complex_number#History P≠NP is not like that.
  - SomeStupidPoint 9y ago
    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.
    - jcranmer 9y ago
      > 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.
    - pvg 9y ago
      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.
- dullcrisp 9y ago
  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.
  - baddox 9y ago
    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.

wtallis 9y ago

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

Sniffnoy 9y ago

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.

zzazzdsa 9y ago

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.