Re:P≠NP proof update
by carbocation on Sunday August 15, 2010 @08:09PM
(#1606326)
Not 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.
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))?