Randomized separations in black-box TFNP
2026-06-03 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors examine how two types of problem-solving methods—deterministic (fixed steps) and randomized (using random choices)—relate to each other in a specific complexity class called TFNP. They develop a new technique that shows these two methods are actually equivalent for reducing certain important TFNP problems to others. This result applies to several well-known subclasses like PPP, PPAD, PPA, and t-PPP. As a consequence, it also improves previous results distinguishing deterministic and randomized approaches in these classes.
TFNPdeterministic reducibilityrandomized reducibilityblack-box reductionPPPPPADPPAcomputational complexitycomplexity classcomplete problems
Authors
Fedor Kiselev
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.