Downward self-reducibility in the total function polynomial hierarchy
Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi · Society for Industrial and Applied Mathematics eBooks · 2026
A problem \(\mathcal{P}\) is considered downward self-reducible, if there exists an efficient algorithm for \(\mathcal{P}\) that is allowed to make queries to only strictly smaller instances of \(\mathcal{P}\). Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem must lie in \(\mathsf{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 \(\mathsf{TFNP}\) and is downward self-reducible, then it must be in \(\mathsf{PLS}\). Moreover, if the problem admits a unique solution then it must be in \(\mathsf{UEOPL}\).