<p>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.</p>

<p>the <a href="http://en.wikipedia.org/wiki/Blum&#39;s_speedup_theorem" rel="nofollow">Blum speedup theorem</a> has been characterized by Goldreich [3] (p149)</p>

<blockquote>
  <p>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 defined (i.e., as the complexity of the best
  algorithm solving this problem).</p>
</blockquote>

<p>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 <a href="http://en.wikipedia.org/wiki/Weierstrass_function" rel="nofollow">Weierstrauss function</a>.</p>

<p>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).</p>

<p>so:</p>

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

<p>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.)</p>

<p>[1] <a href="http://www.scottaaronson.com/blog/?p=1948" rel="nofollow">Is the P vs. NP problem ill-posed? (Answer: no.)</a> Aaronson blog<br>
[2] <a href="http://rjlipton.wordpress.com/2014/05/03/does-program-size-matter/" rel="nofollow">Does program size matter?</a> RJLipton blog<br>
[3] <a href="http://www.wisdom.weizmann.ac.il/~oded/CC/r2.pdf" rel="nofollow">Computational complexity: a conceptual perspective</a> / Goldreich</p>

CC BY-SA 3.0
2014-08-16T04:43:26.587Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-08-16T17:33:30.267Z
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](http://en.wikipedia.org/wiki/Time_hierarchy_theorem)? eg how does one guarantee/ prove that none are in P or NP or any other important complexity classes?
vzn
CC BY-SA 3.0
2014-08-16T19:33:43.363Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-08-17T19:44:48.497Z
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...
vzn
CC BY-SA 3.0
2014-08-19T17:20:16.580Z
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.
Denis
<cc.complexity-theory><reference-request><complexity-classes><time-complexity><big-picture>
proving speedup phenomenon does not apply to any open complexity class separations
vzn
# proving speedup phenomenon does not apply to any open complexity class separations

(Asked by: username_0 on 2014-08-15)

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](http://en.wikipedia.org/wiki/Blum's_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 defined (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](http://en.wikipedia.org/wiki/Weierstrass_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).

so:

> 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.)](http://www.scottaaronson.com/blog/?p=1948) Aaronson blog  
[2] [Does program size matter?](http://rjlipton.wordpress.com/2014/05/03/does-program-size-matter/) RJLipton blog  
[3] [Computational complexity: a conceptual perspective](http://www.wisdom.weizmann.ac.il/~oded/CC/r2.pdf) / Goldreich

**Tags:** cc.complexity-theory, reference-request, complexity-classes, time-complexity, big-picture

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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](http://en.wikipedia.org/wiki/Time_hierarchy_theorem)? eg how does one guarantee/ prove that none are in P or NP or any other important complexity classes?  
> **username_1**: 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.  
> **username_0**: 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...  
> **username_2**: 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.  

---

## 0 answers

