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., ≤_(2-tt)~p, ≤_(ctt)~p. ≤_(dtt)~p). 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: 1. Regarding ≤_m~(log), ≤_(2-tt)~(log), ≤_(dtt)~(log) and ≤_(ctt)~(log), complete sets for PSPACE and EXP are mitotic, and complete sets for NEXP are autoreducible. 2. All ≤_(1-tt)~(log)-complete sets for NL and P are ≤_(2-tt)~(log)-autoreducible, and all ≤_(btt)~(log)-complete sets for NL, P and Δ_k~P are ≤_(log-T)~(log)-autoreducible. 3. There is a ≤_(3-tt)~(log)-complete set for PSPACE that is not even ≤_(btt)~(log)-autoreducible. Using the last result, we conclude that some of our results are hard or even impossible to improve.
展开▼
