ECCC-Report TR22-133https://eccc.weizmann.ac.il/report/2022/133Comments and Revisions published for TR22-133en-usTue, 20 Sep 2022 21:28:17 +0300
Paper TR22-133
| Downward Self-Reducibility in TFNP |
Prahladh Harsha,
Daniel Mitropolsky,
Alon Rosen
https://eccc.weizmann.ac.il/report/2022/133A 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.Tue, 20 Sep 2022 21:28:17 +0300https://eccc.weizmann.ac.il/report/2022/133