Abstract
The empty pigeonhole principle asserts that, if there are more pigeonholes than pigeons, one pigeonhole must be empty. The corresponding class of total function problems contains all of FNP, and its natural problems include applications of the union bound and several well known explicit constructions. Higher up in the polynomial hierarchy, one finds total function problems related to tournaments and the Sauer-Shelah lemma.