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

Strenghtened Theorem 1.3 to show containment in UEOPL and other minor revisions

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