Revision #1 Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

Accepted on: 23rd November 2022 10:32

Downloads: 120

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 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

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

Publication: 20th September 2022 21:28

Downloads: 339

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.

Reason: