<p>The standard comparison-model lower bound for sorting, and most cell probe model lower bounds for data structures, are unconditional (for computing within the model but you could say the same about Turing machine lower bounds) and depend on information theory rather than diagonalization.</p>

CC BY-SA 3.0
2017-11-18T21:23:45.760Z
There are also tons of information-theoretic unconditional lower bounds for various models of distributed computing and parallel computing. No diagonalisation there, either.
Jukka Suomela
CC BY-SA 3.0
2017-11-18T00:59:56.070Z
2017-11-18T00:59:56.070Z
David Eppstein
<p>A tool that can be used to prove negative/impossibility results is the <em>incompressibility method</em>:</p>

<p><strong>Theorem</strong> (Incompressibility Theorem) Let $c$ be a positive integer. For each fixed $y$, every finite set $A$ of cardinality $m$ has at least $m(1-2^{-c})+1$ elements $X$ with $C(x \mid y) \geq \log m - c$</p>

<p>Some well-known applications are: a single tape Turing machine requires $O(n^2)$ steps to decide $\{ ww^R\}$; a DFA cannot recognize $a^n b^n$; impossibility of there being only finitely many primes (and estimates the size of the nth prime correctly to within a log n factor); ....</p>

<p>Ultimately the above theorem relies on the <em>Pigeon Principle</em> which has itself some nice direct applications; for example:</p>

<p><strong>Theorem</strong>: if we color the points in the plane red or blue. Then for any distance $d &gt; 0$, we can find two points at distance $d$ from each other that have the same color.</p>

<p><em>Proof</em>: Pick any equilateral triangle with side equal to $d$ in the real plane. It has three vertices, so by the pigeonhole principle two of them must have the same color, and they are at distance $d$ from each other by construction.</p>

CC BY-SA 3.0
2017-11-19T14:01:56.510Z
It also gives a nice proof of the impossibility of there being only finitely many primes :). (And estimates the size of the nth prime correctly to within a log n factor.)
Joshua Grochow
CC BY-SA 3.0
2017-11-19T22:06:36.397Z
@JoshuaGrochow: oh yes, thanks (I added it to the answer) ... it reminds me that soon or later I should add to my blog an easy-trivial post about this easy-trivial theorem (I've never seen it anywhere): $\exists n_0$ s.t. $n \geq n_0 \land K(n) \geq \log_2(n) \Rightarrow n = a \cdot b$ :-)
Marzio De Biasi
CC BY-SA 3.0
2017-11-18T20:29:53.953Z
2017-11-19T22:00:48.610Z
2017-11-19T22:00:48.610Z
Marzio De Biasi
<p>Lower bounds in non-uniform models of computation, like boolean formulas and circuits, are proved using combinatorial arguments. Some examples are Krapchenko's method using formal complexity measures, Razborov's method of approximations for monotone circuits, the random restriction method, including random restriction + the switching lemma, and depth lower bounds using communication complexity via Karchmer-Wigderson games. You can find lecture notes on this material by <a href="http://courses.csail.mit.edu/6.841/spring09/" rel="noreferrer">Sudan</a>,
 <a href="http://sites.math.rutgers.edu/~sk1233/courses/topics-S13/" rel="noreferrer">Kopparty</a>, <a href="http://www.math.ucsd.edu/~sbuss/CourseWeb/Math262A_2013F/" rel="noreferrer">Buss</a>, <a href="http://www.cs.tau.ac.il/~zwick/scribe-boolean.html" rel="noreferrer">Zwick</a>, among others.</p>

CC BY-SA 3.0
2017-11-19T10:12:10.060Z
Personal favourite answer, I've learnt a lot, thanks. David's and Marzio's are great answers too.
EXPTIME-complete
CC BY-SA 3.0
2017-11-18T04:08:50.930Z
2017-11-18T04:08:50.930Z
Sasho Nikolov
<p>In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-Shapiro's theorem, etc. These techniques work thanks to, or are directly based on, the existence of some diagonal argument (i.e. some program $M$ behaves in the opposite way as its input program $M'$, so $M = M'$ is contradictory). In Complexity, if we want to prove that some problem <em>cannot</em> be computed in some time (regardless of any unproved claims such as e.g. $P \neq NP$), we use arguments which are, ultimately, based on some diagonal argument (e.g. the Time Hierarchy theorem proves $EXPTIME$-complete problems are not in $P$, but that theorem is also proved by using a diagonal argument). </p>

<p>So my question is the following. Are all important impossibility results in Computability and Complexity (actual impossibility, not impossibility up to some unproved result) <em>ultimately</em> due to some diagonal argument? That is, does all our important "impossibility knowledge" in Computability and Complexity come from the fact that programs are powerful enough to execute programs?</p>

<p>The only important impossibility result coming to my mind which is not ultimately due to a diagonal argument is that the Ackermann function is not primitive recursive. Am I missing other important counterexamples of this apparent "rule"?</p>

<p>EDIT (Nov 18): Sorry for implying that my question was particularly focusing on the diagonal argument itself, but I'm more interested on all arguments that rely on the self reference of programs (including the diagonal argument, Berry paradox, etc). For simpler languages (e.g. regular or context-free), we have "structural" impossibility arguments based on how these languages are constructed (e.g. pumping lemmas). However, for recursive or r.e. languages, most of impossibility results strongly rely on the self reference of programs. This is what I meant.</p>

CC BY-SA 3.0
2017-11-17T16:34:56.093Z
Actually the proof that the Ackerman function is not p.r. is a pretty classic application of the diagonal method!
cody
CC BY-SA 3.0
2017-11-17T16:43:22.020Z
I always thought seeing some kind of diagonal argument in the part of that proof concerning the primitive recursive operator would be a little far-fetched... Take e.g. this proof of that result: http://www.cs.tau.ac.il/~nachumd/term/42019.pdf. Am I missing some "hidden" diagonal argument there?
EXPTIME-complete
CC BY-SA 3.0
2017-11-17T16:45:02.223Z
Also: possible duplicate of https://cstheory.stackexchange.com/questions/6575/does-diagonalization-captures-the-essence-of-class-separation
cody
CC BY-SA 3.0
2017-11-17T16:51:23.880Z
Yes, there is a hidden diagonal argument in the proof that a function may not majorize itself, which is referred to here: http://beta.planetmath.org/SuperexponentiationIsNotElementary
cody
CC BY-SA 3.0
2017-11-17T16:58:44.453Z
Probably a bunch of results come from the pigeonhole-principle: Kolmogorov complexity comes to mind ("some strings are not compressible..."). I bet 1$ that all negative results "about a finite domain" have the PP at their root  :-D :-D
Marzio De Biasi
CC BY-SA 3.0
2017-11-17T18:05:27.803Z
Circuit and formula complexity lower bounds are proved using entirely different techniques, like random restrictions and the switching lemma, or communication complexity via Karchmer-Wigderson games
Sasho Nikolov
CC BY-SA 3.0
2017-11-17T21:23:26.007Z
cody: proving binary functions cannot majorize themselves does not require reasoning about programs at all, so that "diagonal" argument does not involve programs simulating themselves (contrarily to the typical computability and complexity typical diagonal arguments I was thinking about here). It's interesting.
EXPTIME-complete
CC BY-SA 3.0
2017-11-17T21:25:42.297Z
Marzio and Sasho: those are pretty good examples indeed.
EXPTIME-complete
CC BY-SA 3.0
2017-11-20T05:09:01.037Z
See also https://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-dep/
Bjørn Kjos-Hanssen
<cc.complexity-theory><computability>
Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?
EXPTIME-complete
# Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

(Asked by: username_0 on 2017-11-17)

In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-Shapiro's theorem, etc. These techniques work thanks to, or are directly based on, the existence of some diagonal argument (i.e. some program $M$ behaves in the opposite way as its input program $M'$, so $M = M'$ is contradictory). In Complexity, if we want to prove that some problem *cannot* be computed in some time (regardless of any unproved claims such as e.g. $P \neq NP$), we use arguments which are, ultimately, based on some diagonal argument (e.g. the Time Hierarchy theorem proves $EXPTIME$-complete problems are not in $P$, but that theorem is also proved by using a diagonal argument).

So my question is the following. Are all important impossibility results in Computability and Complexity (actual impossibility, not impossibility up to some unproved result) *ultimately* due to some diagonal argument? That is, does all our important "impossibility knowledge" in Computability and Complexity come from the fact that programs are powerful enough to execute programs?

The only important impossibility result coming to my mind which is not ultimately due to a diagonal argument is that the Ackermann function is not primitive recursive. Am I missing other important counterexamples of this apparent "rule"?

EDIT (Nov 18): Sorry for implying that my question was particularly focusing on the diagonal argument itself, but I'm more interested on all arguments that rely on the self reference of programs (including the diagonal argument, Berry paradox, etc). For simpler languages (e.g. regular or context-free), we have "structural" impossibility arguments based on how these languages are constructed (e.g. pumping lemmas). However, for recursive or r.e. languages, most of impossibility results strongly rely on the self reference of programs. This is what I meant.

**Tags:** cc.complexity-theory, computability
> **Comments:**
> **username_1**: Actually the proof that the Ackerman function is not p.r. is a pretty classic application of the diagonal method!  
> **username_0**: I always thought seeing some kind of diagonal argument in the part of that proof concerning the primitive recursive operator would be a little far-fetched... Take e.g. this proof of that result: http://www.cs.tau.ac.il/~nachumd/term/42019.pdf. Am I missing some "hidden" diagonal argument there?  
> **username_1**: Also: possible duplicate of https://cstheory.stackexchange.com/questions/6575/does-diagonalization-captures-the-essence-of-class-separation  
> **username_1**: Yes, there is a hidden diagonal argument in the proof that a function may not majorize itself, which is referred to here: http://beta.planetmath.org/SuperexponentiationIsNotElementary  
> **username_2**: Probably a bunch of results come from the pigeonhole-principle: Kolmogorov complexity comes to mind ("some strings are not compressible..."). I bet 1$ that all negative results "about a finite domain" have the PP at their root  :-D :-D  
> **username_3**: Circuit and formula complexity lower bounds are proved using entirely different techniques, like random restrictions and the switching lemma, or communication complexity via Karchmer-Wigderson games  
> **username_0**: cody: proving binary functions cannot majorize themselves does not require reasoning about programs at all, so that "diagonal" argument does not involve programs simulating themselves (contrarily to the typical computability and complexity typical diagonal arguments I was thinking about here). It's interesting.  
> **username_0**: Marzio and Sasho: those are pretty good examples indeed.  
> **username_4**: See also https://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-dep/  

---

## 3 answers

### Answer by username_3 on 2017-11-18. Score: 8 | Accepted answer

Lower bounds in non-uniform models of computation, like boolean formulas and circuits, are proved using combinatorial arguments. Some examples are Krapchenko's method using formal complexity measures, Razborov's method of approximations for monotone circuits, the random restriction method, including random restriction + the switching lemma, and depth lower bounds using communication complexity via Karchmer-Wigderson games. You can find lecture notes on this material by [Sudan](http://courses.csail.mit.edu/6.841/spring09/),
[Kopparty](http://sites.math.rutgers.edu/~sk1233/courses/topics-S13/), [Buss](http://www.math.ucsd.edu/~sbuss/CourseWeb/Math262A_2013F/), [Zwick](http://www.cs.tau.ac.il/~zwick/scribe-boolean.html), among others.

> **Comments:**
> **username_0**: Personal favourite answer, I've learnt a lot, thanks. David's and Marzio's are great answers too.  

---

### Answer by username_5 on 2017-11-18. Score: 9

The standard comparison-model lower bound for sorting, and most cell probe model lower bounds for data structures, are unconditional (for computing within the model but you could say the same about Turing machine lower bounds) and depend on information theory rather than diagonalization.

> **Comments:**
> **username_6**: There are also tons of information-theoretic unconditional lower bounds for various models of distributed computing and parallel computing. No diagonalisation there, either.  

---

### Answer by username_2 on 2017-11-18. Score: 5

A tool that can be used to prove negative/impossibility results is the *incompressibility method*:

**Theorem** (Incompressibility Theorem) Let $c$ be a positive integer. For each fixed $y$, every finite set $A$ of cardinality $m$ has at least $m(1-2^{-c})+1$ elements $X$ with $C(x \mid y) \geq \log m - c$

Some well-known applications are: a single tape Turing machine requires $O(n^2)$ steps to decide $\{ ww^R\}$; a DFA cannot recognize $a^n b^n$; impossibility of there being only finitely many primes (and estimates the size of the nth prime correctly to within a log n factor); ....

Ultimately the above theorem relies on the *Pigeon Principle* which has itself some nice direct applications; for example:

**Theorem**: if we color the points in the plane red or blue. Then for any distance $d > 0$, we can find two points at distance $d$ from each other that have the same color.

*Proof*: Pick any equilateral triangle with side equal to $d$ in the real plane. It has three vertices, so by the pigeonhole principle two of them must have the same color, and they are at distance $d$ from each other by construction.

> **Comments:**
> **username_7**: It also gives a nice proof of the impossibility of there being only finitely many primes :). (And estimates the size of the nth prime correctly to within a log n factor.)  
> **username_2**: @JoshuaGrochow: oh yes, thanks (I added it to the answer) ... it reminds me that soon or later I should add to my blog an easy-trivial post about this easy-trivial theorem (I've never seen it anywhere): $\exists n_0$ s.t. $n \geq n_0 \land K(n) \geq \log_2(n) \Rightarrow n = a \cdot b$ :-)  

---

