Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-133 | 23rd November 2022 10:32

Downward Self-Reducibility in TFNP

RSS-Feed




Revision #1
Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
Accepted on: 23rd November 2022 10:32
Downloads: 2
Keywords: 


Abstract:

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.



Changes to previous version:

Strenghtened Theorem 1.3 to show containment in UEOPL and other minor revisions


Paper:

TR22-133 | 20th September 2022 21:28

Downward Self-Reducibility in TFNP





TR22-133
Authors: Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
Publication: 20th September 2022 21:28
Downloads: 189
Keywords: 


Abstract:

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.


Comment(s):

Comment was removed on Authors: aaa aaaaa
Reason:




ISSN 1433-8092 | Imprint