3 ms·
Say we find an algorithm to solve SAT in O(x^1000). P would equal NP, and yet the set of problems we currently label NP-complete might still be substantially h
by dllthomas 13y ago
Say we find an algorithm to solve SAT in O(x^1000). P would equal NP, and yet the set of problems we currently label NP-complete might still be substantially harder to solve than to verify.