Randomized Separations in Black-Box TFNP
Abstract
We study the relationship between deterministic and randomized black-box reducibility between problems in TFNP. Our main contribution is a general technique that establishes equivalence between these reducibility types from specific TFNP problems to any TFNP problem. In particular, we show that this equivalence holds for reductions from complete problems in PPP, PPAD, PPA, and t-PPP. In turn, it strengthens all known black-box separations, originating from these classes, to randomized separations.
Fields of Study & Subjects
Optimization and Search Problems
Complexity and Algorithms in Graphs
Auction Theory and Applications
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 1 January 2026
- Language
- EN
- Document type
- Preprint