Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOGARITHMIC-SPACE REDUCIBILITY:
Reports tagged with logarithmic-space reducibility:
TR13-047 | 27th March 2013
Christian Gla├čer, Dung Nguyen, Christian Reitwie├čner, Alan Selman, Maximilian Witek

Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Comments: 1

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>




ISSN 1433-8092 | Imprint