P-selective sets,tally languages,and the behavior of polynomial time reducibilities onNP

The notion ofp-selective sets, and tally languages, are used to study polynomial time reducibilities onNP. P-selectivity has the property that a setA belongs to the classP if and only if both _m ^p A andA isp-selective. We prove that for every tally language set inNP there exists a polynomial time equivalent set inNP that isp-selective. From this result it follows that if NEXT DEXT, then polynomial time Turing and many-one reducibilities differ onNP. This research was supported in part by the National Science Foundation under grant MCS 77-23493