Downward Self-Reducibility in TFNP

Abstract

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 \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 \textsc{TFNP}. We show that most natural $\PLS$-complete problems are downward self-reducible and any downward self-reducible problem in \textsc{TFNP} is contained in \textsc{PLS}. Furthermore, if the downward self-reducible problem is in \textsc{TFUP} (i.e. it has a unique solution), then it is actually contained in \textsc{UEOPL}, a subclass of \textsc{CLS}. This implies that if integer factoring is \emph{downward self-reducible} then it is in fact in \textsc{UEOPL}, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.

16 pages, 2 figures