Black-Box PPP Is Not Turing-Closed

The complexity class PPP contains all total search problems many-one reducible to the Pigeon problem, where we are given a succinct encoding of a function mapping n +1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses of TFNP , and has been extensively studied due to the strong connections between its defining problem — the pigeonhole principle — and problems in cryptography, extremal combinatorics, proof complexity, and other fields. However, despite its importance, PPP appears to be less robust than the other important TFNP subclasses. In particular, unlike all other major TFNP subclasses, it was conjectured by Buss and Johnson that PPP is not closed under Turing reductions , and they called for a black-box separation in order to provide evidence for this conjecture. The question of whether PPP contains its Turing closure was further highlighted by Daskalakis in his recent IMU Abacus Medal Lecture. In this work we prove that PPP is indeed not Turing-closed in the black-box setting, affirmatively resolving the above conjecture and providing strong evidence that PPP is not Turing-closed. In fact, we are able to separate PPP from its non-adaptive Turing closure, in which all calls to the Pigeon oracle must be made in parallel. This differentiates PPP from all other important TFNP subclasses, and especially from its closely-related subclass PWPP — defined by reducibility to the weak pigeonhole principle — which is known to be non-adaptively Turing-closed. Our proof requires developing new tools for PPP lower bounds, and creates new connections between PPP and the theory of pseudoexpectation operators used for Sherali-Adams and Sum-of-Squares lower bounds. In particular, we introduce a new type of pseudoexpectation operator that is precisely tailored for lower bounds against black-box PPP , which may be of independent interest.

Authors

• Noah Fleming
• Stefan Grosser
• Toniann Pitassi
• Robert Robere

Keywords

• Pigeonhole Principle
• Proof Complexity
• TFNP
• Turing Reductions