×

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.

MSC:

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)

Citations:

Zbl 0569.03016
PDFBibTeX XMLCite
Full Text: DOI