News for hackers. Stuff that matters.
Re:P≠NP proof update by jacobolus on Sunday August 15, 2010 @08:06PM (#1606318)
> 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))?

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.