ECCC-Report TR22-133https://eccc.weizmann.ac.il/report/2022/133Comments and Revisions published for TR22-133en-usWed, 23 Nov 2022 10:32:37 +0200
Revision 1
| Downward Self-Reducibility in TFNP |
Prahladh Harsha,
Daniel Mitropolsky,
Alon Rosen
https://eccc.weizmann.ac.il/report/2022/133#revision1A 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.Wed, 23 Nov 2022 10:32:37 +0200https://eccc.weizmann.ac.il/report/2022/133#revision1
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