Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-133 | 20th September 2022 21:28

Downward Self-Reducibility in TFNP


Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
Publication: 20th September 2022 21:28
Downloads: 121


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.

ISSN 1433-8092 | Imprint