Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

Question

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.

Answer 1

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, Kopparty, Buss, Zwick, among others.

Answer 2

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.

Answer 3

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.

Answer 4

Actually, the halting problem can be proved without using diagonalization. (And every valid ZFC theorem has a ZFC proof that uses diagonalization...think about it.)

The proof uses the Berry paradox, and proceeds as follows:

Index all Turing machines in a reasonable manner. Assume for the sake of contradiction that the halting problem can be solved. Then consider this algorithm:

f(N) returns the least-indexed Turing machine X s.t. X(X) does not halt and X is not the output of any Turing machine M and input I in under N characters (i.e., M(I) outputs X --> |M| + |I| >= N).

Now, we select sufficiently large N s.t. f(N) must return a description of X that is described precisely by the computation of f(N). If f is computable, then M=f and I=N. For example, we could let N = one googol (10^100).

This suggests that f(N) is not a total function, because for f(10^100), there is no satisfactory output. This contradicts the assumption that the halting problem can be solved. Consider the following pseudocode (which is far less than 10^100 characters when expanded to true source code in C++ or even written as a Turing machine) for f:

f(N)

{

for (int i = 1; ; i++)

{

  if (simulate DoesHalt(UTM(i,i)) == false)

  {

         (simulate all machines and inputs M(I) with |M|+|I|<N)

         if all such inputs do not output i

                 return i;

  }

}

}

Clearly, f halts on all inputs and works properly assuming that the halting the problem can be solved. By the above, we have that the halting problem cannot be solved.

This proof does not use any form of diagonalization. Indeed, you should glance at my question:

Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"

...for some discussion of the fact that many paradoxes may be used in lieu of the liar paradox or Russell's paradox to prove that the halting problem cannot be solved. Some of these non-diagonal-argument paradoxes include the Unexpected Hanging Paradox and (as just described) the Berry Paradox.