Downward self-reducibility in TFNP
summary
Paper proves that if a TFNP search problem is downward self-reducible then it lies in PLS, and that circuit-style d.s.r. with poly-blowup also implies PLS. Proofs simulate the brute-force recursive oracle algorithm as a walk on a state graph and use reversible-computation pebbling to place unique-solution cases into UNIQUE-END-OF-POTENTIAL-LINE/CLS. Consequence: a downward self-reduction for FACTORING (or any unique TFNP problem) would collapse it into UEOPL/CLS, a surprising containment.
AI-written summary · about