According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time complexity of $Ω(n)$. X can be reduced to a certain NP complete problem with quadratic overhead. Because NP-complete problems have Blum's speedup then that means there is an algorithm O with a time complexity of $O(\log n)$. So if we apply the quadratic reduction from X to O then our new algorithm has a time complexity of $O(\log^2 n)$, which contradicts the optimality of X. Then that means NP-complete problems must have asymptotically optimal time complexity.

Is there something wrong with my assumptions? Also, can this kind of problems with speedup be reduced to any complete problem like NP-complete or P-complete problems?


You haven't taken account of the cost of the reduction itself, i.e., the cost of transforming an input for X to an input for O. That might take more than logarithmic time.

I presume by "quadratic overhead" you mean that a problem instance of size $n$ becomes one of size $\Theta(n^2)$. Then the running time of O on that problem is $O(\log n^2) = O(\log n)$, not $O(\log^2 n)$.

The structure of your argument is unclear. You start out with three assumptions (1. $X$ has $\Omega(n)$ complexity, 2. X can be reduced to O with quadratic overhead, 3. all NP-complete problems have Blum's speedup), and attempt to derive a contradiction. If your derivation was valid, this would indeed mean that these three assumptions cannot all be correct; at least one of them must be wrong. From that, you cannot conclude that all NP-complete problems do have Blum speedup; and you cannot conclude that they don't.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.