Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

TLDR

The paper discusses relativized complexity classes, defining P^X and NP^X as the deterministic and nondeterministic polynomial‑time classes relative to an oracle X, and notes related open problems. The study investigates relativized versions of the open question of whether every nondeterministically accepted language in polynomial time can also be recognized deterministically in polynomial time.

Abstract

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 $\mathcal{P}^X (\text{resp. }\mathcal{NP}^X )$ 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 $\mathcal{P}^A = \mathcal{NP}^A $. On the other hand, we construct a recursive set B such that $\mathcal{P}^B \ne \mathcal{NP}^B $. Oracles X are constructed to realize all consistent set inclusion relations between the relativized classes $\mathcal{P}^X $, $\mathcal{NP}^X $, and co $\mathcal{NP}^X $, the family of complements of languages in $\mathcal{NP}^X $. Several related open problems are described.