Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with downward self-reducibility:
TR22-133 | 20th September 2022
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

Downward Self-Reducibility in TFNP

Revisions: 1 , Comments: 1

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

ISSN 1433-8092 | Imprint