Recently Glaßer et al. have shown that for many classes C including PSPACE and NP it holds that all of its nontrivial many-one complete languages are autoreducible. This immediately
raises the question of whether all many-one complete languages are Turing self-reducible for such classes C.
This paper considers a simpler version of this question—whether all PSPACE-complete (NP-complete) languages are length-decreasing
self-reducible. We show that if all PSPACE-complete languages are length-decreasing self-reducible then PSPACE = P and that
if all NP-complete languages are length-decreasing self-reducible then NP = P.
The same type of result holds for many other natural complexity classes. In particular, we show that (1) not all NL-complete
sets are logspace length-decreasing self-reducible, (2) unconditionally not all PSPACE-complete languages are logpsace length-decreasing
self-reducible, and (3) unconditionally not all PSPACE-complete languages are polynomial-time length-decreasing self-reducible.