Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question.

the Blum speedup theorem has been characterized by Goldreich [3] (p149)

A conceptually related phenomenon is of problems that have no optimal algorithm (not even in a very mild sense); that is, every algorithm for these "pathological" problems can be drastically sped-up. It follows that the complexity of these problems can not be defi ned (i.e., as the complexity of the best algorithm solving this problem).

in math, it is not unprecedented that major conjectures have been shown to have "glitches" eg discovery that they are independent of axiomatic systems, etc. also Goldreich reference to "pathological" languages is reminscent of historical consternations in math eg the counterintuitive discovery of functions that are continuous but nowhere differentiable eg the Weierstrauss function.

another angle is that at least one complexity theorist expert Lipton speculates that program size is underanalyzed in TCS and may have surprising aspects,[2] and the Blum speedup theorem seems to fit in with this line of thinking, because the proof construction basically relies on improving the language recognition time based on increasing the size of the TM program (ie like a tradeoff).


how does one show/ prove that no such "pathological" languages are/can be involved in open complexity class separation questions eg P=?NP etc?

am interested in more technical/ mathematical perspectives that avoid handwaving. (eg something more detailed/ substantial than an assertion that the Blum speedup construction is "contrived" etc.)

[1] Is the P vs. NP problem ill-posed? (Answer: no.) Aaronson blog
[2] Does program size matter? RJLipton blog
[3] Computational complexity: a conceptual perspective / Goldreich

  • 1
    $\begingroup$ First, there is Levin's universal search. Second, I don't see what the issue could be. The PvsNP problem is, "If a language is recognized by a non-deterministic polytime Turing machine, is it also recognized by a deterministic polytime Turing machine?" Nothing about this is predicated on the existence of optimal algorithms or optimal complexity. $\endgroup$ – Sasho Nikolov Aug 16 '14 at 4:43
  • $\begingroup$ so-called "pathological" languages are apparently almost not studied at all in TCS except in Blums theorems. but dont they exist somewhere in the Time hierarchy? eg how does one guarantee/ prove that none are in P or NP or any other important complexity classes? $\endgroup$ – vzn Aug 16 '14 at 17:33
  • 1
    $\begingroup$ First, for all languages in NP that depend on all their input bits, you can only achieve polynomial speedup (this is trivial). Second, Levin's universal search technique shows that any problem in NP has an algorithm that is optimal up to poly factors. And finally, the hierarchy theorems show that for any time constructible complexity there exist algorithms of that complexity that cannot be sped up considerably. $\endgroup$ – Sasho Nikolov Aug 16 '14 at 19:33
  • $\begingroup$ are you saying that Blums speedup construction is not time constructible? could be close to an answer... anyway it seems strange at times that there is apparently no further research building on Blums early insights into "pathological" languages... $\endgroup$ – vzn Aug 17 '14 at 19:44
  • $\begingroup$ This speed-up theorem do not endanger the fact that the P vs NP conjecture is well-posed: one is simply asking if there is a polynomial algorithm for SAT. Even if the "optimal complexity" of SAT cannot be well defined, this do not pose any problem for this particular question. $\endgroup$ – Denis Aug 19 '14 at 17:20

Your Answer

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

Browse other questions tagged or ask your own question.