Qualitative relativizations of complexity classes (Q1061119)

A nondeterministic oracle Turing machine (TM) is strong if, relative to each oracle set, for each input x, there is at least one computation that either accepts x or rejects it and there are no contradictory computations. A TM is confluent if for each configuration I, all the computations branching out from I either lead to the same query configuration or do not lead to query configurations at all. A TM is mature if for every nonquery configuration I, if I leads either to an accepting computation or to a rejecting computation without reaching a query configuration, then the computations branching out from I do not contain any query configuration. The main result of this paper states that \(P=NP\cap co\)-Np if and only for every oracle D, \(P(D)=NP_ R(D)\) where \(NP_ R(D)\) is the class of languages accepted by strong, confluent and mature TM's that run in polynomial time. These restrictions are qualitative ones in contrast with quantitative relativizations where the number of accesses to the oracle is restricted. The work also contains an interesting discussion relative to the possibility of weakening the conditions for a positive qualitative relativization of the \(P=?NP\cap co\)-NP problem (no positive quantitative relativization is known).