Hierarchies within TFNP: building blocks and collapses

Abstract

In all well-studied $\mathsf{TFNP}$ subclasses (e.g. $\mathsf{PPP}$ etc.), the canonical complete problem takes as input a polynomial-size circuit $C$ 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, they are 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 \mathsf{FP}$. 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. The exact definitions require some care since the oracle is for a search problem with many possible solutions. To address this, we introduce a strict condition called \emph{Internal Consistency} that underlies the definition. Informally, this condition enforces that, from the perspective of a bounded verifier, the oracle behaves like a function. 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}$.

arXiv commentAdded more discussion about Internal Consistency; Added a correct proof for PPA self-lowness; Corrected small bugs in the proof for PLS self-lowness; Various fixes for typos and bugs. Added AI-Disclosure