QUALITATIVE RELATIVIZATIONS OF COMPLEXITY CLASSES

The nondeterministic polynomial time-bounded oracle Turing machine endowed with designated accepting states and with designated rejecting states is considered, and suitable restrictions R of this device are developed such that P equals NP intersection co-NP if and only if for every oracle D, P(D) equals NP//R(D), where NP//R(D) is the class of languages L an element of NP(D) that are accepted by oracle machines operating with restrictions R. Positive relativizations are obtained for the P equals ? U intersection co-U and U equals ? NP questions also, where U is the class of languages L in NP accepted by nondeterministic machines that operate in polynomial time and that have for each input at most one accepting computation.