2026-07-20T14:51:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25347 2026-03-19T13:03:50Z ddc:004 open_access

Total Search Problems in ZPP Fleming, Noah Grosser, Stefan Jain, Siddhartha Li, Jiawei Ren, Hanlin Shirley, Morgan Yuan, Weiqiang TFNP lossy code randomized proof systems query complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah Fleming and Stefan Grosser and Siddhartha Jain and Jiawei Li and Hanlin Ren and Morgan Shirley and Weiqiang Yuan 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.60 urn:nbn:de:0030-drops-253473 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.60 eng https://creativecommons.org/licenses/by/4.0/legalcode