This paper, "Total Search Problems in $\mathsf{ZPP}$," provides a rigorous foundation for the complexity class $\mathsf{TFZPP}$—the set of search problems where a solution is guaranteed to exist (total) and can be found by a randomized algorithm that never makes a mistake (zero-error).
TL;DR
The authors initiate the first systematic study of $\mathsf{TFZPP}$, proving that while randomized search problems might seem simple, they are surprisingly powerful in "black-box" settings where the problem structure is hidden. They establish a new "zoo" of randomized search problems, linking them to set theory axioms and proof complexity, and show that most natural problems in this class are equivalent to a single core problem: $\text{Lossy-Code}$.
What Problem Does This Paper Address?
In computer science, we often deal with $\mathsf{NP}$ search problems: "Given $X$, find $Y$ such that some condition holds." A sub-category called $\mathsf{TFNP}$ (Total Functional $\mathsf{NP}$) contains problems where a solution is mathematically guaranteed to exist (e.g., finding a prime number between $N$ and $2N$).
Because a solution always exists, these problems cannot be $\mathsf{NP}$-complete unless $\mathsf{NP} = \mathsf{coNP}$. Instead, researchers group them into "syntactic" subclasses based on the mathematical principle that guarantees their totality (like the Pigeonhole Principle for $\mathsf{PPP}$ or local optimality for $\mathsf{PLS}$).
The authors noticed a gap: while randomized algorithms are a staple of modern computing, the class of total search problems solvable by randomized algorithms ($\mathsf{TFZPP}$) lacked a formal taxonomy. Specifically, they wanted to know:
- Is $\mathsf{TFZPP}$ actually "bigger" than deterministic classes in a black-box (query) model?
- What are the "natural" problems that live in $\mathsf{TFZPP}$?
- Can we characterize these problems using the tools of mathematical logic and proof complexity?
Methods
The authors employ several sophisticated techniques from theoretical computer science:
- Black-Box (Query) Complexity: They analyze problems where the input is an oracle (a "black box") you can query. This allows them to prove separations between classes that are currently impossible to prove in the standard "white-box" model.
- Randomized Proof Systems: They extend the known connection between search problems and proof complexity. They show that $\mathsf{TFZPP}$ is characterized by "random tree-like resolution"—a proof system where the "proof" of a problem's totality is a randomized decision tree.
- Bounded Arithmetic: They use Jeřábek’s theory $\mathsf{APC}_1$ (a logic for approximate counting) to prove that complex combinatorial inequalities (like the AM-GM inequality) can be reduced to simpler search problems.
- Herbrandization: A technique from logic used to convert existential statements in first-order logic into search problems.
Datasets
As a theoretical paper, it does not use empirical datasets. Instead, it defines and analyzes several new and existing formal search problems:
- $\text{Lossy-Code}$: Finding an element not in the range of a compression/decompression pair.
- $\text{Nephew}$: A new problem derived from "axioms of infinity" in set theory.
- $\text{Empty-Child}$: Finding a leaf in a binary tree where every node is supposed to have two children.
- $\text{AM-GM-LC}$: A search problem based on the Arithmetic Mean-Geometric Mean inequality.
Key Insights and Ideas
- Randomness is Power (in the Black Box): In a standard setting, we suspect $\mathsf{P} = \mathsf{BPP}$ (randomness doesn't help much). However, this paper proves that for total search problems in the black-box model, randomized algorithms are strictly more powerful than deterministic ones. They show $\mathsf{TFZPP}$ is not contained in major classes like $\mathsf{PPA}$, $\mathsf{PPP}$, or $\mathsf{PLS}$ in this setting.
- The "Nephew" Candidate: They introduce $\text{Nephew}$, a problem where "your nephew's grandparent is not your parent." This problem is fascinating because it originates from logic axioms that describe infinite sets, yet it sits comfortably within $\mathsf{TFZPP}$ for finite sets.
- The "Lossy-Code" Magnet: A major "aha" moment is that almost every natural randomized search problem the authors found—even those based on complex inequalities like AM-GM or the Inclusion-Exclusion principle—eventually reduces to the $\text{Lossy-Code}$ problem. This suggests $\text{Lossy-Code}$ is the "natural" core of randomized search.
Key Results
- Separation Theorem: $\mathsf{TFZPP}^{dt}$ is not contained in any uniformly generated $\mathsf{TFNP}^{dt}$ class (like $\mathsf{PLS}$ or $\mathsf{PPP}$) unless $\mathsf{NP}$ is in quasi-polynomial time.
- Explicit Hardness: They provide explicit (polynomial-time constructible) problems that are in $\mathsf{TFZPP}$ but are not in $\mathsf{PPP}$ or $\mathsf{PLS}$ in the black-box model.
- Equivalences: They prove $\text{Empty-Child} \equiv \text{Lossy-Code}$ and show that $\text{Dense-Linear-Ordering}$ also reduces to $\text{Lossy-Code}$.
- Taxonomy: The paper provides a "Zoo" (Figure 1) mapping the relationships between these randomized classes and classical ones.
Limitations and Future Work
- The Nephew Conjecture: While they show $\text{Nephew}$ is in $\mathsf{TFZPP}$, they conjecture it is not reducible to $\text{Lossy-Code}$. Proving this would show that $\mathsf{TFZPP}$ has internal structure and isn't just "everything reduces to $\text{Lossy-Code}$."
- Bertrand-Chebyshev: The problem of finding a prime between $N$ and $2N$ is known to be in $\mathsf{TFZPP}$ (white-box), but its black-box complexity remains elusive. The authors couldn't find a "natural" randomized class it belongs to.
- White-Box vs. Black-Box: The separations proven here only hold in the black-box model. Whether these classes are distinct in the standard model remains a massive open question tied to the $\mathsf{P}$ vs. $\mathsf{NP}$ circle of problems.
Summary updated