Hierarchies within TFNP: building blocks and collapses

Abstract

In all well-studied $\mathsf{TFNP}$ subclasses (e.g. $\mathsf{PPA},\mathsf{PPP}$ etc.), the canonical complete problem takes as input a polynomial-size circuit $C:\{0,1{\}}^n\to \{0,1{\}}^m$ whose input-output behavior implicitly encodes an exponentially large object $G$, i.e. $C$ is the succinct (polynomial-size) representation of the exponential size object $G$. The goal is to find some particular substructure in $G$ which can be confirmed in polynomial time using queries to $C$. We initiate the study of classes of the form ${\mathsf{A}}^{\mathsf{B}}$ where both $\mathsf{A}$ and $\mathsf{B}$ are $\mathsf{TFNP}$ subclasses. In particular, we define complete problems for these classes that take as input a circuit $C$ which is allowed oracle gates to another $\mathsf{TFNP}$ class. Beyond introducing definitions for $\mathsf{TFNP}$ oracle problems, our specific technical contributions include showing that several $\mathsf{TFNP}$ subclasses are self-low and hence their corresponding hierarchies collapse. In particular, $\mathsf{PP}{\mathsf{A}}^{\mathsf{PPA}}=\mathsf{PPA}$, $\mathsf{PL}{\mathsf{S}}^{\mathsf{PLS}}=\mathsf{PLS}$, and $\mathsf{LOSS}{\mathsf{Y}}^{\mathsf{LOSSY}}=\mathsf{LOSSY}$. As an immediate consequence, we derive that when reducing to $\mathsf{PPA}$, one can always assume access to $\mathsf{PPA}$ -- and therefore factoring -- oracle gates. In addition to introducing a variety of hierarchies within $\mathsf{TFNP}$ that merit study in their own right, these ideas introduce a novel approach for classifying computational problems within $\mathsf{TFNP}$ and proving black-box separations. For example, we observe that the problem of deterministically generating large prime numbers, which has long resisted classification in a $\mathsf{TFNP}$ subclass, is in $\mathsf{PP}{\mathsf{P}}^{\mathsf{PPP}}$ under the Generalized Riemann Hypothesis.