R_1-tt^SN(NP) Distinguishes Robust Many-One and Turing Completeness
<|reference_start|>R_1-tt^SN(NP) Distinguishes Robust Many-One and Turing Completeness: Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class-namely a downward closure of NP, \rsnnp - has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world this class has 2-truth-table complete sets but lacks 1-truth-table complete sets. As part of the groundwork for our result, we prove that \rsnnp has many equivalent forms having to do with ordered and parallel access to $\np$ and $\npinterconp$.<|reference_end|>
@article{hemaspaandra1999r_{1-tt}^{sn}(np),
    title={R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness},
    author={Edith Hemaspaandra, Lane A. Hemaspaandra, and Harald Hempel},
    journal={Theory of Computing Systems, 31, 307-325, 1998},
    year={1999},
    number={earlier version appears as UR-CS-TR-96-635},
    archivePrefix={arXiv},
    eprint={cs/9910003},
    primaryClass={cs.CC}
}