Total Search Problems in $\mathsf{ZPP}$

Abstract

We initiate a systematic study of $\mathsf{TFZPP}$, the class of total $\mathsf{NP}$ search problems solvable by polynomial time randomized algorithms. $\mathsf{TFZPP}$ contains a variety of important search problems such as $\text{Bertrand-Chebyshev}$ (finding a prime between $N$ and $2N$), refuter problems for many circuit lower bounds, and $\text{Lossy-Code}$. The $\text{Lossy-Code}$ problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas. While $\mathsf{TFZPP}$ collapses to $\mathsf{FP}$ under standard derandomization assumptions in the white-box setting, we are able to separate $\mathsf{TFZPP}$ from the major $\mathsf{TFNP}$ subclasses in the black-box setting. In fact, we are able to separate it from every uniform $\mathsf{TFNP}$ class assuming that $\mathsf{NP}$ is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box $\mathsf{TFNP}$ to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of $\mathsf{TFZPP}$ problems. We highlight a problem called $\text{Nephew}$, originating from an infinity axiom in set theory. We show that $\text{Nephew}$ is in $\mathsf{PWPP}\cap \mathsf{TFZPP}$ and conjecture that it is not reducible to $\text{Lossy-Code}$. Intriguingly, except for some artificial examples, most other black-box $\mathsf{TFZPP}$ problems that we are aware of reduce to $\text{Lossy-Code}$.

ITCS 2026. Abstract shortened due to constraints