3 ms·
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? Obvious
by 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.)