Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Total search problems in ZPP

Fleming, Noah LU orcid ; Grosser, Stefan ; Jain, Sigghartha ; Li, Jiawei ; Ren, Hanlin ; Shirley, Morgan LU orcid and Yuan, Weiqiang (2026) In Leibniz International Proceedings in Informatics (LIPIcs) 362. p.1-60
Abstract
We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The 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 TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP... (More)
We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The 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 TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions.

Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code:

- We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code.

- We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007).

- Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code. (Less)
Please use this url to cite or link to this publication:
author
; ; ; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
series title
Leibniz International Proceedings in Informatics (LIPIcs)
editor
Saraf, Shubhangi
volume
362
article number
60
pages
1 - 60
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
external identifiers
  • scopus:105037313311
ISSN
1868-8969
ISBN
978-3-95977-410-9
DOI
10.4230/LIPIcs.ITCS.2026.60
language
English
LU publication?
yes
id
413fcb64-aede-4dfc-9b73-1677aa22ec0d
date added to LUP
2026-06-18 15:36:15
date last changed
2026-08-18 07:37:56
@inproceedings{413fcb64-aede-4dfc-9b73-1677aa22ec0d,
  abstract     = {{We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas.<br/><br/>While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions.<br/><br/>Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code:  <br/><br/>- We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. <br/><br/>- We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007).<br/><br/>- Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.}},
  author       = {{Fleming, Noah and Grosser, Stefan and Jain, Sigghartha and Li, Jiawei and Ren, Hanlin and Shirley, Morgan and Yuan, Weiqiang}},
  booktitle    = {{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}},
  editor       = {{Saraf, Shubhangi}},
  isbn         = {{978-3-95977-410-9}},
  issn         = {{1868-8969}},
  language     = {{eng}},
  pages        = {{1--60}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics (LIPIcs)}},
  title        = {{Total search problems in ZPP}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ITCS.2026.60}},
  doi          = {{10.4230/LIPIcs.ITCS.2026.60}},
  volume       = {{362}},
  year         = {{2026}},
}