4 ms·
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 failin
by 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 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.