5 ms·

Betting on whether P=NP

amichail 17y ago
How is trying to prove that P=NP distinctly different from trying to prove that P!=NP? Perhaps while trying to prove P=NP, you finally realize why it can't be the case and end up proving that P!=NP instead?
- brazzy 17y ago
  P=NP can be proven by example. All you need is one concrete algorithm. Proving that no such algorithm can exist is a whole different beast and not likely to be the result of trying to construct e.g. a factoring algorithm and failing.
  - amichail 17y ago
    Proving that no such algorithm can exist is a whole different beast and not likely to be the result of trying to construct e.g. a factoring algorithm and failing. Why is this obvious? Perhaps the search for an algorithm would give you a key insight as to why P!=NP.
    - brazzy 17y ago
      Possible, but unlikely. Look at Fermat's last theorem, a much simpler statement. All it would have taken for a positive proof would have been four numbers. Trying to find them by brute force failed and, really obviously, yielded absolutely no insights. The actual negative proof took a brilliant mind, years of complete dedication that might have turned out to be wasted, and the combination of two formerly completely unrelated fields of mathematics.
      - roundsquare 17y ago
        Also, just take a look at some examples of lower bounds on a problem. Even the simplest one I know (sorting): http://www.cs.colorado.edu/~karl/2270.spring03/sorting.html http://www.cs.colorado.edu/~karl/2270.spring03/sorting.html is much tougher than showing the running time of an algorithm.
  - waldrews 17y ago
    Subtle point: we already have an algorithm that would sovle NP-complete problems in P time if P=NP; it's just that we don't have a proof that it works that way. See for example http://en.wikipedia.org/wiki/P_%3D_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_%3D_NP_problem#Polynomial-tim...
  - DrJokepu 17y ago
    Fortunately, Greek mathematicians have discovered approaches to handle "beasts" like that thousands of years ago; it's called "reductio ad absurdum" (proof by contradiction). If someone shown that P=NP implied a contradiction, that would disprove the conjecture.
    - brazzy 17y ago
      Good luck finding something that the mere existence of an algorithm with a sub-exponential complexity could contradict. And I didn't state that proving a negative is impossible, just that it's completely different from proving a positive by example and unlikely to benefit from failed attempts to find such an example.
btilly 17y ago
The thesis is well presented, but I don't buy it. Suppose that P=NP, but the algorithm you find has running time O(n^100). How does the world change? Obviously not much because nobody could actually run it. A theoretician would respond that if Moore's law continued long enough, then eventually this would be practical. However physicists tell us that there is a minimum amount of energy released by irreversibly flipping a bit, from which we can calculate the minimum amount of energy required to run this algorithm for an interesting data set. That minimum makes this algorithm infeasible for the foreseeable future, no matter what advances we make in technology. While we say that we believe that P!=NP, the bet that we're making in real life is that NP-complete problems are computationally infeasible. (That said factoring has never been proven to be NP-complete, so we could come up with a good factoring algorithm without being able to solve NP-complete problems.)

How is trying to prove that P=NP distinctly different from trying to prove that P!=NP? Perhaps while trying to prove P=NP, you finally realize why it can't be the case and end up proving that P!=NP instead?

brazzy 17y ago
P=NP can be proven by example. All you need is one concrete algorithm. Proving that no such algorithm can exist is a whole different beast and not likely to be the result of trying to construct e.g. a factoring algorithm and failing.
- amichail 17y ago
  Proving that no such algorithm can exist is a whole different beast and not likely to be the result of trying to construct e.g. a factoring algorithm and failing. Why is this obvious? Perhaps the search for an algorithm would give you a key insight as to why P!=NP.
  - brazzy 17y ago
    Possible, but unlikely. Look at Fermat's last theorem, a much simpler statement. All it would have taken for a positive proof would have been four numbers. Trying to find them by brute force failed and, really obviously, yielded absolutely no insights. The actual negative proof took a brilliant mind, years of complete dedication that might have turned out to be wasted, and the combination of two formerly completely unrelated fields of mathematics.
    - roundsquare 17y ago
      Also, just take a look at some examples of lower bounds on a problem. Even the simplest one I know (sorting): http://www.cs.colorado.edu/~karl/2270.spring03/sorting.html http://www.cs.colorado.edu/~karl/2270.spring03/sorting.html is much tougher than showing the running time of an algorithm.
- waldrews 17y ago
  Subtle point: we already have an algorithm that would sovle NP-complete problems in P time if P=NP; it's just that we don't have a proof that it works that way. See for example http://en.wikipedia.org/wiki/P_%3D_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_%3D_NP_problem#Polynomial-tim...
- DrJokepu 17y ago
  Fortunately, Greek mathematicians have discovered approaches to handle "beasts" like that thousands of years ago; it's called "reductio ad absurdum" (proof by contradiction). If someone shown that P=NP implied a contradiction, that would disprove the conjecture.
  - brazzy 17y ago
    Good luck finding something that the mere existence of an algorithm with a sub-exponential complexity could contradict. And I didn't state that proving a negative is impossible, just that it's completely different from proving a positive by example and unlikely to benefit from failed attempts to find such an example.

btilly 17y ago

The thesis is well presented, but I don't buy it. Suppose that P=NP, but the algorithm you find has running time O(n^100). How does the world change? Obviously not much because nobody could actually run it. A theoretician would respond that if Moore's law continued long enough, then eventually this would be practical. However physicists tell us that there is a minimum amount of energy released by irreversibly flipping a bit, from which we can calculate the minimum amount of energy required to run this algorithm for an interesting data set. That minimum makes this algorithm infeasible for the foreseeable future, no matter what advances we make in technology. While we say that we believe that P!=NP, the bet that we're making in real life is that NP-complete problems are computationally infeasible. (That said factoring has never been proven to be NP-complete, so we could come up with a good factoring algorithm without being able to solve NP-complete problems.)