Total Search Problems in $\mathsf{ZPP}$
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917115675541504 |
|---|---|
| author | Fleming, Noah Grosser, Stefan Jain, Siddhartha Li, Jiawei Ren, Hanlin Shirley, Morgan Yuan, Weiqiang |
| author_facet | Fleming, Noah Grosser, Stefan Jain, Siddhartha Li, Jiawei Ren, Hanlin Shirley, Morgan Yuan, Weiqiang |
| contents | We initiate a systematic study of ${\sf TFZPP}$, the class of total ${\sf NP}$ search problems solvable by polynomial time randomized algorithms. ${\sf 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 ${\sf TFZPP}$ collapses to ${\sf FP}$ under standard derandomization assumptions in the white-box setting, we are able to separate ${\sf TFZPP}$ from the major ${\sf TFNP}$ subclasses in the black-box setting. In fact, we are able to separate it from every uniform ${\sf TFNP}$ class assuming that ${\sf NP}$ is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box ${\sf TFNP}$ to randomized proof systems and randomized reductions.
Next, we turn to developing a taxonomy of ${\sf 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 ${\sf TFZPP}$ problems that we are aware of reduce to $\text{Lossy-Code}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01138 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Total Search Problems in $\mathsf{ZPP}$ Fleming, Noah Grosser, Stefan Jain, Siddhartha Li, Jiawei Ren, Hanlin Shirley, Morgan Yuan, Weiqiang Computational Complexity We initiate a systematic study of ${\sf TFZPP}$, the class of total ${\sf NP}$ search problems solvable by polynomial time randomized algorithms. ${\sf 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 ${\sf TFZPP}$ collapses to ${\sf FP}$ under standard derandomization assumptions in the white-box setting, we are able to separate ${\sf TFZPP}$ from the major ${\sf TFNP}$ subclasses in the black-box setting. In fact, we are able to separate it from every uniform ${\sf TFNP}$ class assuming that ${\sf NP}$ is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box ${\sf TFNP}$ to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of ${\sf 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 ${\sf TFZPP}$ problems that we are aware of reduce to $\text{Lossy-Code}$. |
| title | Total Search Problems in $\mathsf{ZPP}$ |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2512.01138 |