On polynomial-time truth-table reducibility of intractable sets to P-selective sets

The existence of setsnot being _tt^P-reducible to low sets is investigated for several complexity classes such as UP, NP, the polynomial-time hierarchy, PSPACE, and EXPTIME. The p-selective sets are mainly considered as a class of low sets. Such investigations were done in many earlier works, but almost all of these have dealt withpositive reductions in order to imply the strongest consequence such as P=NP under the assumption that all sets in NP are polynomial-time reducible to low sets. Currently, there seems to be some difficulty in obtaining the same strong results undernonpositive reducibilities. The purpose of this paper is to develop a useful technique to show for many complexity classes that if each set in the class is polynomial-time reducible to a p-selective set via anonpositive reduction, then the class is already contained in P. The following results are shown in this paper.(1) If each set in UP is _tt^P-reducible to a p-selective set, then P=UP.(2) If each set in NP is _tt^P-reducible to a p-selective set, then P=FewP and R=NP.(3) If each set in ₂^P is _tt^P-reducible to a p-selective set, then P=NP.(4) If each set in PSPACE is _tt^P-reducible to a p-selective set, then P=PSPACE.(5) There is a set in EXPTIME that is not _tt^P-reducible to any p-selective set.It remains open whether P=NP follows from a weaker assumption that each set in NP is _tt^P-reducible to a p-selective set.