Positive Relativizations of Complexity Classes

From MaRDI portal





In order to address complexity questions such as P \(=? NP\) or P \(=? PSPACE\) one is lead to investigate complexity classes relativized to an oracle set A, but there exist oracle sets A and B such that \(P(A)=NP(A)\) and \(P(B)=NP(B)\) [\textit{T. Baker, J. Gill}, and \textit{R. Solovay}, SIAM J. Comput. 4, 431-442 (1975; Zbl 0323.68033)]. The main positive results of the current paper are: 1. \(P=PSPACE\) iff \(P(A)=PQUERY(A)\) for every set A, and 2. \(P=NP\) iff \(P(A)=NPC(A)\), where PQUERY(A) is the set of all languages recognizable by deterministic Turing machines with oracle A using only polynomial space and a polynomial number of calls on the oracle, and where NPC(A) is the class of languages recognizable in polynomial time by non-deterministic Turing machines with oracle A and subject to the restriction (called confluent) that from any configuration at most one computation leads to a (actually, the next) call on the oracle. These relativization results, among others in the paper, show that relativization can be used to establish positive relations between the unrelativized complexity classes.




Cited in
(35)








This page was built for publication: Positive Relativizations of Complexity Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3343440)