Quantitative relativizations of complexity classes. (English) Zbl 0599.03041

Consider the following open problems: (i) \(P=?NP\); (ii) \(NP=?co\)-NP; (iii) \(P=?PSPACE\); (iv) \(NP=?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 \(P(A)=NP(A)\) and P(B)\(\neq NP(B)\). We study restrictions R on both the deterministic and also the nondeterministic polynomial time-bounded oracle machines such that the following holds: \(P=NP\) if and only if for every set A, \(P_ R(A)=NP_ R(A)\). The restrictions are ”quantitative” in the sense that the size 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.


03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)


Zbl 0569.03016
Full Text: DOI