5 ms·

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 possi

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.
  - baddox 9y ago
    The analogy is not meant to be applied further than “sometimes we invent new mathematical tools solve problems that were impossible to solve previously.”
    - pvg 9y ago
      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).
      - alphaalpha101 9y ago
        >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). That's not a 'counter analogy'. It's the same analogy. Nobody is saying 'we have solved other problems therefore this one is solvable even though it appears not to be'. People are saying 'we can't say it's impossible just because it looks to be impossible'.
- 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.

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.
- baddox 9y ago
  The analogy is not meant to be applied further than “sometimes we invent new mathematical tools solve problems that were impossible to solve previously.”
  - pvg 9y ago
    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).
    - alphaalpha101 9y ago
      >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). That's not a 'counter analogy'. It's the same analogy. Nobody is saying 'we have solved other problems therefore this one is solvable even though it appears not to be'. People are saying 'we can't say it's impossible just because it looks to be impossible'.
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.