4 ms·
> If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Knuth
by andrewla 8y ago
> If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time).
Knuth himself, for example, has casually expressed the opinion (not a proof) that P=NP in the past. When you say "as easily" it belies the nature of polynomial time questions. If it turns out that we can produce an algorithm for 3SAT that is O(n^1e72), then that will in fact prove that P=NP. But this does not make any practical problems "easy".
- CJefferson 8y agoNo need for n^1e72, a SAT instance with a couple of hundred variables can usually be solved easily, industrial instances are often hundreds of thousands of variables. Even a O(n^10) algorithm would be of MASSIVE theoretical interest, but almost no practical value.
- mcguire 8y agohttps://www.scottaaronson.com/blog/?p=122 https://www.scottaaronson.com/blog/?p=122 See #5. And... https://www.scottaaronson.com/blog/?p=3095 https://www.scottaaronson.com/blog/?p=3095