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.
My point is simply to show that even linear-time problems may be computationally intractable.