Positive Relativizations of Complexity Classes
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.
- Qualitative relativizations of complexity classes
- On bounded query machines
- Relativized alternation and space-bounded computation
- On sparse oracles separating feasible complexity classes
- Positive relativizations of the \(P=?\) NP problem
- Restricted relativizations of probabilistic polynomial time
- A positive relativization of polynomial time versus polylog space
- Positive versions of polynomial time
- Sets with small generalized Kolmogorov complexity
- A note on logspace optimization
- Positive relativizations for log space computability
- Refining Nondeterminism in Relativizations of Complexity Classes
- scientific article; zbMATH DE number 4019036 (Why is no real title available?)
- scientific article; zbMATH DE number 4172379 (Why is no real title available?)
- Some Observations on Separating Complexity Classes
- scientific article; zbMATH DE number 3885883 (Why is no real title available?)
- scientific article; zbMATH DE number 3868613 (Why is no real title available?)
- Complexity of Counting the Optimal Solutions
- scientific article; zbMATH DE number 3940729 (Why is no real title available?)
- Quantitative Relativizations of Complexity Classes
- scientific article; zbMATH DE number 4011940 (Why is no real title available?)
- Characterizations of reduction classes modulo oracle conditions
- On relativizations with restricted number of accesses to the oracle set
- scientific article; zbMATH DE number 4099277 (Why is no real title available?)
- scientific article; zbMATH DE number 4106269 (Why is no real title available?)
- On Tally Relativizations of $BP$-Complexity Classes
- A survey of one-way functions in complexity theory
- scientific article; zbMATH DE number 500314 (Why is no real title available?)
- scientific article; zbMATH DE number 3995053 (Why is no real title available?)
- ANALYSIS OF QUANTUM FUNCTIONS
- The strong exponential hierarchy collapses
- Computing functions with parallel queries to NP
- Complexity classes of equivalence problems revisited
- Complexity of counting the optimal solutions
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
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)