ECCC-Report TR13-047https://eccc.weizmann.ac.il/report/2013/047Comments and Revisions published for TR13-047en-usSun, 12 May 2013 21:17:35 +0300
Comment 1
| Related work fixed |
Dung Nguyen,
Alan Selman,
Christian Glaßer,
Christian Reitwießner,
Maximilian Witek
https://eccc.weizmann.ac.il/report/2013/047#comment1The claim for 2-tt mitoticity in Theorem 5.11.1, every 2-tt complete set for EXP is 2-tt mitotic, was already mentioned in H. Buhrman and L. Torenvliet, " A Post's program for complexity theory", Bulletin of the EATCS 85, pp41--51, 2005.Sun, 12 May 2013 21:17:35 +0300https://eccc.weizmann.ac.il/report/2013/047#comment1
Paper TR13-047
| Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions |
Christian Glaßer,
Dung Nguyen,
Christian Reitwießner,
Alan Selman,
Maximilian Witek
https://eccc.weizmann.ac.il/report/2013/047We 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., polynomial-time 2-tt, ctt, dtt reducibility).
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 log-space many-one, 2-tt, dtt and ctt reducibility, complete sets for PSPACE and EXP are mitotic, and complete sets for NEXP are autoreducible.
- All log-space 1-tt-complete sets for NL and P are log-space 2-tt-autoreducible, and all log-space btt-complete sets for NL, P and the delta-levels of the PH are log-space Turing-autoreducible.
- There is a log-space 3-tt-complete set for PSPACE that is not even log-space btt-autoreducible.
Using the last result, we conclude that some of our results are hard or even impossible to improve.
Wed, 27 Mar 2013 17:13:47 +0200https://eccc.weizmann.ac.il/report/2013/047