<p>If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for <em>proof by contradiction</em>. There are concepts in TCS which are not proof by contradiction, and therefore, in particular, are not instances of the pigeon-hole principle. There are also proofs by contradiction where the pigeon-hole principle is necessary but not sufficient.</p>

<p><strong>My personal opinion:</strong> It is fruitful to take apart a proof and see why it works: what are the ingredients? When you understand the ingredients, a proof ceases to be a monolithic line of reasoning and "symbol-pushing", and it will become a modular object with identifiable moving parts, which you can then reuse between proofs, eventually making your own ones. As a corollary, you are right to become wary when all your results derive most of their power from one core lemma (such as PHP in this case), because it means that you are probably working within the narrow confines of that lemma, and you may benefit from learning and incorporating other theorems from other fields into your work (See also <a href="https://terrytao.wordpress.com/career-advice/learn-the-limitations-of-your-tools/" rel="noreferrer">Terry Tao's advice</a>, and <a href="https://terrytao.wordpress.com/career-advice/learn-and-relearn-your-field/" rel="noreferrer">more advice</a> on this topic)</p>

<p>Hence it is useful to identify which proofs, and which parts of those proofs, are the PHP or versions and extensions thereof. At the same time, however, we must be careful to mark any and every type of counting argument as a PHP-argument, and even more careful to discard any proof that incorporates a pigeon-hole argument. Usually, the counting argument is only the closing argument to "plant the flag on the mountain", but the counting argument is used at a point that you can only get to when you've already done the bulk of the work, when "you've climbed the mountain", which is arguing <em>why</em> the one set is bigger than the other. The IP=PSPACE example is instructive here: It is true that there is a counting argument involved, but the more sophisticated part of the proof is arguing that Arthur's random choices usually lead to acceptance. This invokes the Fundamental Theorem of Algebra, which is typically proved using complex analysis via properties of holomorphic functions (<a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra" rel="noreferrer">Wikipedia</a> lists four proofs, none of which can be said to boil down to PHP).</p>

<p>An extreme analogy: every line of every proof is an instance of modus ponens. But would be unfair to object that proofs simply boil down to modus ponens.</p>

<hr>

<p>The most immediate concept that is not a proof by contradiction is algorithms.</p>

<p>For example, the algorithm of the Cook-Levin proof that SAT is NP-Complete transforms a (Turing Machine, input)-pair to a Boolean Circuit, or to a 3-CNF formula, according to taste. The proof then argues that this transformation preserves both soundness and completeness. This is not a pigeon-hole type argument, because it is <em>constructive</em> in the sense that they argue that something is possible, whereas the pigeon-hole principle argues that something is impossible.</p>

<p>More generally, all results which state that a language <span class="math-container">$L$</span> is complete for a complexity class <span class="math-container">$\mathcal{C}$</span> are constructive in this sense.</p>

<hr>

<p><strong>Is IP=PSPACE a pigeon-hole type argument?</strong></p>

<p>The part of the proof of the sumcheck's protocol's soundness amounts, in the end, to saying "<em>The polynomial does not have enough zeroes, relative to the size of the field, to fool Arthur with good probability.</em>" According to taste, this sentence may or may not be an instance of the pigeon-hole principle. </p>

<p>The protocol's soundness relies on, not just that the field is bigger than the number of the polynomial's zeroes, but it relies on the fact that the ratio of non-zeroes to zeros is large enough (sufficiently large for Arthur to guess a non-zero in each iteration of the protocol, with <span class="math-container">$1-\frac{1}{poly(n)}$</span> probability). This reasoning about ratios goes beyond the pigeon-hole principle: I would say this part of the proof is by counting, but not by pigeon-hole principle.</p>

<p>The proof argues that the protocol terminates in polynomial time. To this end, it requires polynomial-time randomized algorithms for guessing a large prime and computing <span class="math-container">$+,-,\times$</span> modulo large primes. The proof also argues that the arithmetization of a Boolean formula preserves its behaviour on the Boolean cube. These ingredients are non-trivial and necessary. Hence to this end, the pigeon-hole principle may be necessary, but is not sufficient.</p>

<hr>

<p><strong>Is the time hierarchy theorem a pigeon-hole type argument?</strong></p>

<p>The proofs of the time- and space hierarchy theorems are not necessarily pigeon-hole type, even though they are proof by contradiction. However, they are identical in structure to (perhaps inspired by) Cantor's proof that some infinities are bigger than others, establishing a pigeon-hole principle for infinite sets (in particular, I have taught a class where I proved these two theorems at the same time, on two adjacent black boards, walking over from one to the other for every new line). Cantor's proof is diagonalization, and from diagonalization follows a type of pigeon hole principle for infinite sets. However, there are two things to be said against counting the time hierarchy theorem as a pigeon-hole type argument. First, the proof is by diagonalization, not by counting. Second, there are many more ingredients in the proof, without which, it would not go through; for instance, a simulation of one Turing Machine by another; for stronger versions, an <em>efficient</em> simulation, which in turn uses such ingredients as shifting the tape to achieve low amortized time complexity. The diagonalization is <em>necessary but not sufficient</em>.</p>

CC BY-SA 4.0
2018-11-19T03:24:45.297Z
+1 beautiful answer. Minor quibble: the fact that a univariate polynomial of degree $d$ has *at most* $d$ roots follows from the division algorithm for polynomials, and does not need the fundamental theorem of algebra. The holomorphic function proofs are used to show that every polynomial over $\mathbb{C}$ has a root.
Sasho Nikolov
CC BY-SA 4.0
2018-11-18T13:31:13.893Z
2018-11-18T13:31:13.893Z
Lieuwe Vinkhuijzen
<p>Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient or is it just Complexity theory as we know it today outside quantum Complexity theory and undecidability just some part of large scale of things inferable from counting and Pigeonhole and where does quantum complexity theory fit in (essentially I am asking what kind of structures have been applicable and essential or can we do away with structures completely and reduce complexity theory to counting and pigeonhole?)?</p>

CC BY-SA 4.0
2018-11-18T02:05:20.090Z
I find the premise unbelievable to the point of silliness. How are Cook-Levin, IP=PSPACE, the PCP theorem, the Goldreich-Levin theorem, or the natural proofs barrier, to name a few examples from the book, a consequence of the pigeonhole principle? Also, how can you be equating TCS with what's in a book on Complexity Theory? You are aware that there is a lot of TCS that's not a part of complexity theory, right?
Sasho Nikolov
CC BY-SA 4.0
2018-11-18T02:10:17.887Z
Why do you claim natural proofs is not pigeonhole? It seems to me a typical case except they push the difficult part of 'refuting or proving existence of one way functions' under the rug as an hypothesis? IP=PSPACE seems like pigeonhole as well. I do not know if anyone has attempted to put everything you state in complexity theory under pigeonhole principle and I would not be surprised if that is possible.
Turbo
CC BY-SA 4.0
2018-11-18T03:09:49.890Z
How on earth is IP = PSPACE "pigeonhole in disguise"? I need some explanation.
Sasho Nikolov
CC BY-SA 4.0
2018-11-18T03:17:04.843Z
Look at the mechanics of the proof that goes through polynomials.
Turbo
CC BY-SA 4.0
2018-11-18T03:27:45.977Z
I know the proof well enough. The sumcheck protocol uses the argument that a univariate polynomial of degree $d$ on a large enough field is unlikely to be zero on a random point. This is not the pigeonhole principle. Maybe you think that every argument that counts something is just the pigeonhole principle? And even leaving that aside, there are many other ideas in this proof, the biggest one being arithmetization. No one would call the Riemann mapping theorem "just the Cauchy integral formula in disguise" because a proof of it uses the Cauchy formula.
Sasho Nikolov
CC BY-SA 4.0
2018-11-19T00:24:36.007Z
@SashoNikolov There is more than counting and PH. Some proofs as IP=PSPACE invoke some structure which is beyond counting arguments. I still think this is a fairly reasonable post. I will accept answer.
Turbo
CC BY-SA 4.0
2018-11-19T11:42:15.093Z
Isn't the proof of undecidability pigeonhole? The diagonal argument just says that the infinite (uncountable) number of pigeons is larger than the infinite (countable) number of holes.
Lamine
CC BY-SA 4.0
2018-11-19T19:05:15.143Z
I have yet to see a proof in type theory that uses the pigeonhole principle. Well, complexity theory is more combinatorics, so using the pigeonhole principle is useful. Type theory has nothing to do with counting, so the pigeonhole principle does not even make any sense.
xrq
CC BY-SA 4.0
2018-11-19T20:30:16.033Z
I disagree that this is a reasonable question as currently worded, since it's based on a blatantly false premise. However, the well-written accepted answer redeems it.
Sasho Nikolov
CC BY-SA 4.0
2018-11-21T15:04:56.580Z
I've seen the quip that all inequalities in analysis essentially boil down to $x^2\ge0$.
Aryeh
CC BY-SA 4.0
2018-11-21T17:37:41.817Z
@Aryeh I guess if the inequalities involve polynomials, then this is the content of the [Positivstellensatz](http://www.mit.edu/~parrilo/ecc03_course/06_positivstellensatz.pdf)?
Sasho Nikolov
CC BY-SA 4.0
2018-11-22T00:35:43.443Z
Questions about the (minimal) set of axioms that are sufficient to prove major results in complexity theory are investigated formally in the framework of bounded arithmetic. Specifically, the theory of *approximate counting* $APC_1$ (using indeed the [weak] *pigeonhole principle* for p-time functions as an axiom) was investigated by [Jerabek 2007](http://users.math.cas.cz/~jerabek/papers/apx.pdf) and later works. I think that this theory can carry out many constructions in complexity theory. See for example [Muller and Pich](https://eccc.weizmann.ac.il/report/2017/144/), and references there.
Iddo Tzameret
CC BY-SA 4.0
2018-11-22T00:43:06.940Z
(Of course, there is a difference between asking for the type of "arguments" used in proofs and the type of axioms they necessitate, but sometimes these questions are close.)
Iddo Tzameret
CC BY-SA 4.0
2018-11-22T04:25:34.090Z
@IddoTzameret Thank you for the insightful comment. May be Emil Jerabek has better insights then.
Turbo
<cc.complexity-theory><reference-request><big-picture><big-list><proofs>
Possible to do Complexity theory with only counting and Pigeonhole
Turbo
# Possible to do Complexity theory with only counting and Pigeonhole

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

Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient or is it just Complexity theory as we know it today outside quantum Complexity theory and undecidability just some part of large scale of things inferable from counting and Pigeonhole and where does quantum complexity theory fit in (essentially I am asking what kind of structures have been applicable and essential or can we do away with structures completely and reduce complexity theory to counting and pigeonhole?)?

**Tags:** cc.complexity-theory, reference-request, big-picture, big-list, proofs

> **Comments:**
> **username_1**: I find the premise unbelievable to the point of silliness. How are Cook-Levin, IP=PSPACE, the PCP theorem, the Goldreich-Levin theorem, or the natural proofs barrier, to name a few examples from the book, a consequence of the pigeonhole principle? Also, how can you be equating TCS with what's in a book on Complexity Theory? You are aware that there is a lot of TCS that's not a part of complexity theory, right?  
> **username_0**: Why do you claim natural proofs is not pigeonhole? It seems to me a typical case except they push the difficult part of 'refuting or proving existence of one way functions' under the rug as an hypothesis? IP=PSPACE seems like pigeonhole as well. I do not know if anyone has attempted to put everything you state in complexity theory under pigeonhole principle and I would not be surprised if that is possible.  
> **username_1**: How on earth is IP = PSPACE "pigeonhole in disguise"? I need some explanation.  
> **username_0**: Look at the mechanics of the proof that goes through polynomials.  
> **username_1**: I know the proof well enough. The sumcheck protocol uses the argument that a univariate polynomial of degree $d$ on a large enough field is unlikely to be zero on a random point. This is not the pigeonhole principle. Maybe you think that every argument that counts something is just the pigeonhole principle? And even leaving that aside, there are many other ideas in this proof, the biggest one being arithmetization. No one would call the Riemann mapping theorem "just the Cauchy integral formula in disguise" because a proof of it uses the Cauchy formula.  
> **username_0**: @SashoNikolov There is more than counting and PH. Some proofs as IP=PSPACE invoke some structure which is beyond counting arguments. I still think this is a fairly reasonable post. I will accept answer.  
> **username_2**: Isn't the proof of undecidability pigeonhole? The diagonal argument just says that the infinite (uncountable) number of pigeons is larger than the infinite (countable) number of holes.  
> **username_3**: I have yet to see a proof in type theory that uses the pigeonhole principle. Well, complexity theory is more combinatorics, so using the pigeonhole principle is useful. Type theory has nothing to do with counting, so the pigeonhole principle does not even make any sense.  
> **username_1**: I disagree that this is a reasonable question as currently worded, since it's based on a blatantly false premise. However, the well-written accepted answer redeems it.  
> **username_4**: I've seen the quip that all inequalities in analysis essentially boil down to $x^2\ge0$.  
> **username_1**: @username_4 I guess if the inequalities involve polynomials, then this is the content of the [Positivstellensatz](http://www.mit.edu/~parrilo/ecc03_course/06_positivstellensatz.pdf)?  
> **username_5**: Questions about the (minimal) set of axioms that are sufficient to prove major results in complexity theory are investigated formally in the framework of bounded arithmetic. Specifically, the theory of *approximate counting* $APC_1$ (using indeed the [weak] *pigeonhole principle* for p-time functions as an axiom) was investigated by [Jerabek 2007](http://users.math.cas.cz/~jerabek/papers/apx.pdf) and later works. I think that this theory can carry out many constructions in complexity theory. See for example [Muller and Pich](https://eccc.weizmann.ac.il/report/2017/144/), and references there.  
> **username_5**: (Of course, there is a difference between asking for the type of "arguments" used in proofs and the type of axioms they necessitate, but sometimes these questions are close.)  
> **username_0**: @IddoTzameret Thank you for the insightful comment. May be Emil Jerabek has better insights then.  

---

## 1 answers

### Answer by username_6 on 2018-11-18. Score: 17

If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for *proof by contradiction*. There are concepts in TCS which are not proof by contradiction, and therefore, in particular, are not instances of the pigeon-hole principle. There are also proofs by contradiction where the pigeon-hole principle is necessary but not sufficient.

**My personal opinion:** It is fruitful to take apart a proof and see why it works: what are the ingredients? When you understand the ingredients, a proof ceases to be a monolithic line of reasoning and "symbol-pushing", and it will become a modular object with identifiable moving parts, which you can then reuse between proofs, eventually making your own ones. As a corollary, you are right to become wary when all your results derive most of their power from one core lemma (such as PHP in this case), because it means that you are probably working within the narrow confines of that lemma, and you may benefit from learning and incorporating other theorems from other fields into your work (See also [Terry Tao's advice](https://terrytao.wordpress.com/career-advice/learn-the-limitations-of-your-tools/), and [more advice](https://terrytao.wordpress.com/career-advice/learn-and-relearn-your-field/) on this topic)

Hence it is useful to identify which proofs, and which parts of those proofs, are the PHP or versions and extensions thereof. At the same time, however, we must be careful to mark any and every type of counting argument as a PHP-argument, and even more careful to discard any proof that incorporates a pigeon-hole argument. Usually, the counting argument is only the closing argument to "plant the flag on the mountain", but the counting argument is used at a point that you can only get to when you've already done the bulk of the work, when "you've climbed the mountain", which is arguing *why* the one set is bigger than the other. The IP=PSPACE example is instructive here: It is true that there is a counting argument involved, but the more sophisticated part of the proof is arguing that Arthur's random choices usually lead to acceptance. This invokes the Fundamental Theorem of Algebra, which is typically proved using complex analysis via properties of holomorphic functions ([Wikipedia](https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra) lists four proofs, none of which can be said to boil down to PHP).

An extreme analogy: every line of every proof is an instance of modus ponens. But would be unfair to object that proofs simply boil down to modus ponens.

---

The most immediate concept that is not a proof by contradiction is algorithms.

For example, the algorithm of the Cook-Levin proof that SAT is NP-Complete transforms a (Turing Machine, input)-pair to a Boolean Circuit, or to a 3-CNF formula, according to taste. The proof then argues that this transformation preserves both soundness and completeness. This is not a pigeon-hole type argument, because it is *constructive* in the sense that they argue that something is possible, whereas the pigeon-hole principle argues that something is impossible.

More generally, all results which state that a language $L$ is complete for a complexity class $\mathcal{C}$ are constructive in this sense.

---

**Is IP=PSPACE a pigeon-hole type argument?**

The part of the proof of the sumcheck's protocol's soundness amounts, in the end, to saying "*The polynomial does not have enough zeroes, relative to the size of the field, to fool Arthur with good probability.*" According to taste, this sentence may or may not be an instance of the pigeon-hole principle.

The protocol's soundness relies on, not just that the field is bigger than the number of the polynomial's zeroes, but it relies on the fact that the ratio of non-zeroes to zeros is large enough (sufficiently large for Arthur to guess a non-zero in each iteration of the protocol, with $1-\frac{1}{poly(n)}$ probability). This reasoning about ratios goes beyond the pigeon-hole principle: I would say this part of the proof is by counting, but not by pigeon-hole principle.

The proof argues that the protocol terminates in polynomial time. To this end, it requires polynomial-time randomized algorithms for guessing a large prime and computing $+,-,\times$ modulo large primes. The proof also argues that the arithmetization of a Boolean formula preserves its behaviour on the Boolean cube. These ingredients are non-trivial and necessary. Hence to this end, the pigeon-hole principle may be necessary, but is not sufficient.

---

**Is the time hierarchy theorem a pigeon-hole type argument?**

The proofs of the time- and space hierarchy theorems are not necessarily pigeon-hole type, even though they are proof by contradiction. However, they are identical in structure to (perhaps inspired by) Cantor's proof that some infinities are bigger than others, establishing a pigeon-hole principle for infinite sets (in particular, I have taught a class where I proved these two theorems at the same time, on two adjacent black boards, walking over from one to the other for every new line). Cantor's proof is diagonalization, and from diagonalization follows a type of pigeon hole principle for infinite sets. However, there are two things to be said against counting the time hierarchy theorem as a pigeon-hole type argument. First, the proof is by diagonalization, not by counting. Second, there are many more ingredients in the proof, without which, it would not go through; for instance, a simulation of one Turing Machine by another; for stronger versions, an *efficient* simulation, which in turn uses such ingredients as shifting the tape to achieve low amortized time complexity. The diagonalization is *necessary but not sufficient*.

> **Comments:**
> **username_1**: +1 beautiful answer. Minor quibble: the fact that a univariate polynomial of degree $d$ has *at most* $d$ roots follows from the division algorithm for polynomials, and does not need the fundamental theorem of algebra. The holomorphic function proofs are used to show that every polynomial over $\mathbb{C}$ has a root.  

---

