Paper Info
Title
Autoreducibility of complete sets for log-space and polynomial-time reductions
Abstract
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 truth-table reductions (e.g., $\leq^{p}_{2-tt},\leq^{p}_{ctt},\leq^{p}_{dtt}$). Moreover, we start a systematic study of logarithmic-space autoreducibility and mitoticity which enables us to also consider P and smaller classes. Among others, we obtain the following results: · Regarding $\leq^{log}_{m}, \leq^{log}_{2-tt}, \leq^{log}_{dtt}$ and $\leq^{log}_{ctt}$, complete sets for PSPACE and EXP are mitotic, and complete sets for NEXP are autoreducible. · All $\leq^{log}_{1-tt}$-complete sets for NL and P are $\leq^{log}_{2-tt}$-autoreducible, and all $\leq^{log}_{btt}$-complete sets for NL, P and $\Delta^{p}_{k}$ are $\leq^{log}_{log-T}$-autoreducible. · There is a $\leq^{log}_{3-tt}$-complete set for PSPACE that is not even $\leq^{log}_{btt}$-autoreducible. Using the last result, we conclude that some of our results are hard or even impossible to improve.
Year
DOI
Venue
2013
10.1007/978-3-642-39206-1_40
ICALP
Keywords
DocType
Volume
polynomial-time reducibility notion,last result,new mitoticity,logarithmic-space autoreducibility,classes exp,complete set,polynomial-time reduction,following result,autoreducibility result,different polynomial-time,logarithmic-space reducibility notion
Journal
20
ISSN
Citations 
PageRank 
0302-9743
4
0.47
References 
Authors
7
5
Name
Order
Citations
PageRank
Christian Glaßer117524.52
Dung T. Nguyen213410.29
Christian Reitwießner3394.81
Alan L. Selman41532185.40
Maximilian Witek5253.71