Post #2298377

@stylus@social.afront.org I realise that when a mere mortal says "Knuth is wrong!" it's likely that the mortal is wrong, but even so … _surely_ no such upper bound M can exist on the complexity of everything in NP? The existence of M is a stronger claim than "just" P=NP. Certainly if P=NP then you could nominate a specific NP-complete problem, say 3SAT, and solve any other NP problem in polynomial time by reducing it to an instance of 3SAT and solving that. The reduction process would have to take polynomial time; the resulting instance of 3SAT would have to have size polynomial in the size of the original problem; and solving 3SAT would have some polynomial complexity. But only one of those three polynomials has a uniformly bounded degree, across all NP problems: _after_ you've reduced your problem to 3SAT then it must be solvable in O(n^K) time for some fixed K relating to 3SAT itself. I don't think there's any rule that says there can't be problems in NP for which the reduction _to_ 3SAT takes an arbitrarily high-degree polynomial amount of time, or raises the size of the problem to an arbitrary power. If so, then you'd still be able to find a problem in NP that required at least n^R time, for arbitrarily large R, and there wouldn't be a single M bounding the whole lot. In particular, if M existed, then not only would all the NP problems be soluble in time n^M, but so would all the P problems. There'd be no such thing as a Θ(n^{M+1}) problem. That seems _very_ unlikely – _surely_ there's some nice simple construction that can give you a polynomial-time problem of minimum degree R, for any R?