3 ms·
> What if someone proved that all NP problems could be solved in O(n) time? You’re quite confused. NP is (at least) a superset of P, and not all problems in P
by jacobolus 16y ago
> What if someone proved that all NP problems could be solved in O(n) time?
You’re quite confused. NP is (at least) a superset of P, and not all problems in P can be solved in linear time (for example, sorting an arbitrarily long list of random numbers). I think you meant something like O(n^(1000^1000))?
- carbocation 16y agoNot confused, though you are correct that we already know that at least some NP cannot be solved in linear time given that NP is a superset of P. I should have phrased things more narrowly. My point is simply to show that even linear-time problems may be computationally intractable.