Downward self-reducibility in the total function polynomial hierarchy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908466884378624 |
|---|---|
| author | Gajulapalli, Karthik Ghentiyala, Surendra Li, Zeyong Saraogi, Sidhant |
| author_facet | Gajulapalli, Karthik Ghentiyala, Surendra Li, Zeyong Saraogi, Sidhant |
| contents | 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 also 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}$.
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 ($\mathsf{TFΣ_i^P}$). 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 $\mathsf{TFΣ_i^P}$ which admits a randomized downward self-reduction with access to a $\mathsf{Σ_{i-1}^P}$ oracle must be in $\mathsf{PLS}^{\mathsf{Σ_{i-1}^P}}$. If the problem has \textit{essentially unique solutions} then it lies in $\mathsf{UEOPL}^{\mathsf{Σ_{i-1}^P}}$.
As one (out of many) application of our framework, we get new upper bounds for the problems $\mathrm{Range Avoidance}$ and $\mathrm{Linear Ordering Principle}$ and show that they are both in $\mathsf{UEOPL}^{\mathsf{NP}}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19108 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Downward self-reducibility in the total function polynomial hierarchy Gajulapalli, Karthik Ghentiyala, Surendra Li, Zeyong Saraogi, Sidhant Computational Complexity Data Structures and Algorithms 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 also 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}$. 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 ($\mathsf{TFΣ_i^P}$). 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 $\mathsf{TFΣ_i^P}$ which admits a randomized downward self-reduction with access to a $\mathsf{Σ_{i-1}^P}$ oracle must be in $\mathsf{PLS}^{\mathsf{Σ_{i-1}^P}}$. If the problem has \textit{essentially unique solutions} then it lies in $\mathsf{UEOPL}^{\mathsf{Σ_{i-1}^P}}$. As one (out of many) application of our framework, we get new upper bounds for the problems $\mathrm{Range Avoidance}$ and $\mathrm{Linear Ordering Principle}$ and show that they are both in $\mathsf{UEOPL}^{\mathsf{NP}}$. |
| title | Downward self-reducibility in the total function polynomial hierarchy |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.19108 |