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?)?

  • 5
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Nov 18 '18 at 2:05
  • 2
    $\begingroup$ How on earth is IP = PSPACE "pigeonhole in disguise"? I need some explanation. $\endgroup$ – Sasho Nikolov Nov 18 '18 at 3:09
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 18 '18 at 3:27
  • 2
    $\begingroup$ 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. $\endgroup$ – Lamine Nov 19 '18 at 11:42
  • 4
    $\begingroup$ 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 and later works. I think that this theory can carry out many constructions in complexity theory. See for example Muller and Pich, and references there. $\endgroup$ – Iddo Tzameret Nov 22 '18 at 0:35

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, and more advice 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 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.

  • 6
    $\begingroup$ +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. $\endgroup$ – Sasho Nikolov Nov 19 '18 at 3:24

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.