TR22-133 Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

Publication: 20th September 2022 21:28

Downloads: 121

Keywords:

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.