2 ms·
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
by carbocation 16y ago
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.