8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually the proof that the Ackerman function is not p.r. is a pretty classic application of the diagonal method! $\endgroup$ – cody Nov 17 '17 at 16:34
  • 1
    $\begingroup$ Also: possible duplicate of cstheory.stackexchange.com/questions/6575/… $\endgroup$ – cody Nov 17 '17 at 16:45
  • 1
    $\begingroup$ Yes, there is a hidden diagonal argument in the proof that a function may not majorize itself, which is referred to here: beta.planetmath.org/SuperexponentiationIsNotElementary $\endgroup$ – cody Nov 17 '17 at 16:51
  • 1
    $\begingroup$ 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 $\endgroup$ – Marzio De Biasi Nov 17 '17 at 16:58
  • 3
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Nov 17 '17 at 18:05
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Personal favourite answer, I've learnt a lot, thanks. David's and Marzio's are great answers too. $\endgroup$ – EXPTIME-complete Nov 19 '17 at 10:12
9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ There are also tons of information-theoretic unconditional lower bounds for various models of distributed computing and parallel computing. No diagonalisation there, either. $\endgroup$ – Jukka Suomela Nov 18 '17 at 21:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Joshua Grochow Nov 19 '17 at 14:01
  • 1
    $\begingroup$ @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$ :-) $\endgroup$ – Marzio De Biasi Nov 19 '17 at 22:06
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It means that what f(N) returns is exactly what I described in the description of how f computes functions. Check out the Wikipedia article on the Berry paradox if this confuses you (or feel free to ask additional questions in the comments). I meant to write "i" instead of "X" and will fix that shortly. And yes, my wordy phrasing of "X is not the output of any M" could be simplified as you suggest. Aside from these minor points, I hope you agree that my answer is correct. I will address your other comment in a moment. $\endgroup$ – Philip White Nov 17 '17 at 21:19
  • 2
    $\begingroup$ What seems to be left unanswered that the OP was interested in, perhaps fitting for a separate question, is whether we can avoid self reference entirely. $\endgroup$ – Kurt Mueller Nov 17 '17 at 22:32
  • 2
    $\begingroup$ I think I agree with the others: the essence of the Berry paradox is still the same as the essence of Cantor diagonalization. See e.g. cstheory.stackexchange.com/q/21917/129, cstheory.stackexchange.com/q/2853/129, cstheory.stackexchange.com/q/37824/129. $\endgroup$ – Joshua Grochow Nov 17 '17 at 22:37
  • 2
    $\begingroup$ @PhilipWhite: Your idea of "diagonalization" is pretty restrictive (the Wikipedia page is about Cantor's diagonal argument, not about diagonalization itself). There is a much broader meaning you can give to "diagonalization", and is related to Lavwere's fixpoint theorem, as pointed out above by Joshua Grochow. The word "diagonal" comes from the so-called diagonal morphism $A\to A\times A$, which exists in any category with products. The idea underlying diagonalization is taking a map $e:A\times A\to B$ in which the two arguments are of the same type but of different nature (...) $\endgroup$ – Damiano Mazza Nov 20 '17 at 16:59
  • 2
    $\begingroup$ (...) and precomposing it with the diagonal map to get $e':A\to B$. This map $e'$ is then used to show that all maps $B\to B$ have a fixpoint or, contrapositively, to show that $e$ cannot exist because there is at least one map $B\to B$ without fixpoints. The diagonal map sends $X$ to $\langle X,X\rangle$; in your case, you are precomposing this map to the "evaluation map", obtaning $X(X)$. It is not a matter of self-referentiality, just a matter of using the same object twice, at two different "semantic" levels. $\endgroup$ – Damiano Mazza Nov 20 '17 at 17:06

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.