Downward self-reducibility in the total function polynomial hierarchy

A problem P is considered downward self-reducible, if there exists an efficient algorithm for P that is allowed to make queries to only strictly smaller instances of P. Downward selfreducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem must lie in PSPACE. Harsha, Mitropolsky and Rosen [ITCS, 2023] initiated the study of downward self reductions in the case of search problems. They showed the following interesting collapse: if a problem is in TFNP and also downward self-reducible, then it must be in PLS. Moreover, if the problem admits a unique solution then it must be in UEOPL.

We demonstrate that this represents just the tip of a much more general phenomenon, which holds for even harder search problems that lie higher up in the total function polynomial hierarchy (TFΣ P i ). In fact, even if we allow our downward self-reduction to be much more powerful, such a collapse will still occur. We show that any problem in TFΣ P i which admits a randomized downward self-reduction with access to a Σ P i-1 oracle must be in PLS Σ P i-1 . If the problem has essentially unique solutions then it lies in UEOPL Σ P i-1 . As an application of our framework, we get new upper bounds for the problems Range Avoidance and Linear Ordering Principle and show that they are both in UEOPL NP , a particularly small subclass of TFΣ P 2 . As a corollary of the powerful Range Avoidance framework, we get that a host of explicit construction problems like constructing rigid matrices, Ramsey graphs, hard truth tables against fixed polynomial size circuits are all in UEOPL NP . This appears to be an orthogonal containment to the results by Chen, Hirahara and Ren [STOC 2024], Li [STOC 2024], and Korten and Pitassi [FOCS 2024] that put the Linear Ordering Principle and hence Range Avoidance in FS 2 P.

In the third level of the polynomial hierarchy, we show that King, the only candidate problem not known to collapse to any smaller sub-class of TFΣ P 3 , indeed collapses to PLS Σ P 2 . Even more surprisingly, we give a ZPP Σ P 2 algorithm for King. This refutes the idea proposed in Kleinberg, Korten, Mitropolosky, and Papadimitriou [ITCS 2021] that King is in a class in and by itself.

Along the way, we highlight the power of our framework by giving alternate proofs of PLS and UEOPL membership for several important problems: the P-matrix linear complementarity problem, finding a winning strategy in a parity game, finding a Tarski fixed point, and the S-Arrival problem. These proofs only rely on the fact that the natural recursive algorithms for