Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with logspace reducibility:
TR13-188 | 13th December 2013
Christian Gla├čer, Maximilian Witek

Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:
- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.
- For P, the delta-levels of ... more >>>

ISSN 1433-8092 | Imprint