4 ms·
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
by 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 agoProving 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 agoPossible, 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 agoAlso, 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 agoSubtle 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 agoFortunately, 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 agoGood 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.