Quantitative Relativizations of Complexity Classes
Ronald V. Book, Timothy J. Long, Alan L. Selman · SIAM Journal on Computing · 1984
Consider the following open problems: (i) ${\text{P}} = ? {\text{ NP}}$ (ii) ${\text{NP}} = ? {\text{ co-NP}}$; (iii) ${\text{P}} = ? {\text{ PSPACE}}$; (iv) ${\text{NP}} = ? {\text{ PSPACE}}$. In this paper we study these four problems from a particular point of view. To illustrate our approach, consider the first problem. It is known that there exist recursive sets A and B such that ${\text{P}}(A) = {\text{NP}}(A)$ and ${\text{P}}(B) e {\text{NP}}(B)$. We study restrictions R on both the deterministic and also the nondeterministic polynomial time-bounded oracle machines such that the following holds: ${\text{P}} = {\text{NP}}$ if and only if for every set A, ${\text{P}}_R (A) = {\text{NP}}_R (A)$. The restrictions are “quantitative” in the sense that the size of the set of strings queried by the oracle in computations of a machine on an input is bounded by a polynomial in the length of the input. We study several different ways of specifying such quantitative restrictions, each of which has the desired property.