Quantitative Relativizations of Complexity Classes
Authors:
- Ronald V. BookRBRonald V. Book
- Timothy J. LongTLTimothy J. Long
- Alan L. SelmanASAlan L. Selman
- 1 August 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (3) , 461-487
Abstract
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) \ne {\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.
Keywords
This publication has 23 references indexed in Scilit:
- Oracle-dependent properties of the lattice of NP setsTheoretical Computer Science, 1983
- Relativizing Time, Space, and Time-SpaceSIAM Journal on Computing, 1982
- Bounded query machines: On NP and PSPACETheoretical Computer Science, 1981
- Bounded query machines: On NP() and NPQUERY()Theoretical Computer Science, 1981
- On counting problems and the polynomial-time hierarchyTheoretical Computer Science, 1980
- Indexings of subrecursive classesTheoretical Computer Science, 1980
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979
- On relativizing auxiliary pushdown machinesTheory of Computing Systems, 1979
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- Turing machines and the spectra of first-order formulasThe Journal of Symbolic Logic, 1974