Possible to do Complexity theory with only counting and Pigeonhole

Question

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

Answer 1

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.