Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-188 | 13th December 2013 16:39

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

RSS-Feed




TR13-188
Authors: Christian Glaßer, Maximilian Witek
Publication: 28th December 2013 13:13
Downloads: 3748
Keywords: 


Abstract:

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 the PH, NEXP: each logspace many-one-complete set is a disjoint union of two logspace 2-tt-complete sets.
- For PSPACE: each polynomial-time dtt-complete set is a disjoint union of two polynomial-time dtt-complete sets.



ISSN 1433-8092 | Imprint