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 \rightarrow \{ 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$.

While such formulations have proven fruitful in the $\mathsf{TFNP}$ literature, it is arguably insufficient to characterize much of $\mathsf{TFNP}$. For example, for any object $G$ whose succinct description requires one to factor integers, it seems we cannot represent it by a circuit $C$ under the widely believed assumption that $\mathrm{Factor} \notin \P$.

To address this, 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. For example, $\mathsf{PPP}^{\mathsf{PPA}}$ would involve finding a collision in a circuit $C^{\mathsf{PPA}}: [N] \rightarrow [N-1]$ where $C$ has oracle gates to a $\mathsf{PPA}$-complete problem. We can then iterate this construction to obtain hierarchies (e.g. $\mathsf{PPP^{(PPP^{PPP})}}$). Here, we uncover a rich structure of hierarchies and collapses. However, these definitions require some care since, unlike a class like $\mathsf{PPP^{NP}}$, where the $\mathsf{NP}$ oracle defines a function, in $\mathsf{PPP^{PPA}}$, the oracle is for a search problem with many possible solutions. Intuitively, the definitions we introduce quantify over all possible instantiations of the $\mathsf{PPA}$ oracle. The hierarchies we obtain are contained in $\cc{TFNP}$ and therefore much lower than the other generalization of $\mathsf{TFNP}$ subclasses ($\mathsf{TFPH}$) recently defined in Kleinberg, Korten, Mitropolsky, and Papadimitriou (ITCS'21).

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{PPA^{PPA}} = \mathsf{PPA}$, $\mathsf{PLS^{PLS}} = \mathsf{PLS}$, and $\mathsf{LOSSY^{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{PPP^{\mathsf{PPP}}}$ under the Generalized Riemann Hypothesis.

Updated abstract and some expositions. Updated the definition of the classes.

We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since unlike a class like ${PPA^{NP}}$, where the ${NP}$ oracle defines a function, in ${PPA^{PPP}}$, the oracle is for a search problem with many possible solutions. Intuitively, the definitions we introduce quantify over all possible instantiations of the ${PPP}$ oracle.

With these notions in place, we then show that several ${TFNP}$ subclasses are self-low. In particular, ${PPA^{PPA}} = {PPA}$, ${PLS^{PLS}} = {PLS}$, and ${LOSSY^{LOSSY}} = {LOSSY}$. These ideas introduce a novel approach for classifying computational problems within ${TFNP}$, such as the problem of deterministically generating large primes.