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 clos ure of NP, R-1-tt(SN)(NP)-has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world th is class has 2-truth-table complete sets but lacks 1-truth-table compl ete sets. As part of the groundwork for our result, we prove that R-1- tt(SN)(NP) has many equivalent forms having to do with ordered and par allel access to NP and NP boolean AND coNP.