Key points are not available for this paper at this time.
We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized deterministically in polynomial time. For any set X, let PX (resp. NPX) be the class of languages accepted in polynomial time by deterministic (resp. nondeterministic) query machines with oracle X. We construct a recursive set A such that PA = NPA. On the other hand, we construct a recursive set B such that PB NPB. Oracles X are constructed to realize all consistent set inclusion relations between the relativized classes PX, NPX, and co NPX, the family of complements of languages in NPX. Several related open problems are described.
Baker et al. (Mon,) studied this question.