Downward Self-Reducibility in TFNP

A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in $\text{textsc}PSPACE$. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution – that is, the downward self-reducible problems in $\text{textsc}TFNP$. We show that most natural $\text{PLS}$-complete problems are downward self-reducible and any downward self-reducible problem in $\text{textsc}TFNP$ is contained in $\text{textsc}PLS$. Furthermore, if the downward self-reducible problem is in $\text{textsc}TFUP$ (i.e. it has a unique solution), then it is actually contained in $\text{textsc}UEOPL$, a subclass of $\text{textsc}CLS$. This implies that if integer factoring is \emph{downward self-reducible} then it is in fact in $\text{textsc}UEOPL$, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.