Relativized alternation and space-bounded computation
From MaRDI portal
Baker, Gill and Solovay showed in 1975 that there exist double relativizations of the \(P=? NP\) question. This is generally taken as evidence that the underlying unrelativized problem is difficult to solve. In this paper it is argued that the failure of unrelativized simulation in the relativized case is due to unequal oracle access mechanisms. The alternation model is therefore considered. Relative to this model nearly all known Turing machine simulations hold with respect to any oracle set.
Recommendations
Cites work
- A note on relativized log space
- A second step toward the polynomial hierarchy
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Alternating Pushdown and Stack Automata
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Computational Complexity of Probabilistic Turing Machines
- scientific article; zbMATH DE number 3825168 (Why is no real title available?)
- scientific article; zbMATH DE number 3723866 (Why is no real title available?)
- scientific article; zbMATH DE number 3992933 (Why is no real title available?)
- scientific article; zbMATH DE number 3995053 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3399210 (Why is no real title available?)
- Limitations on Separating Nondeterministic Complexity Classes
- Log space machines with multiple oracle tapes
- On Approximation Algorithms for # P
- On bounded query machines
- On counting problems and the polynomial-time hierarchy
- On relativizing auxiliary pushdown machines
- On Time Versus Space
- Oracles for Deterministic Versus Alternating Classes
- Parallel computation and the NC hierarchy relativized
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Parity, circuits, and the polynomial-time hierarchy
- Real-Time Simulation of Multihead Tape Units
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Relations Between Time and Tape Complexities
- Relationships between nondeterministic and deterministic tape complexities
- Relativization of questions about log space computability
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized polynomial hierarchies extending two levels
- Relativized Questions Involving Probabilistic Algorithms
- Some results on relativized deterministic and nondeterministic time hierarchies
- Space-bounded hierarchies and probabilistic computations
- Space-bounded simulation of multitape turing machines
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
Cited in
(18)- A measure of relativized space which is faithful with respect to depth
- A survey of space complexity
- Nonerasing, counting, and majority over the linear time hierarchy
- Space-efficient informational redundancy
- Computation by interaction for space-bounded functional programming
- Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
- scientific article; zbMATH DE number 3940729 (Why is no real title available?)
- scientific article; zbMATH DE number 4092777 (Why is no real title available?)
- A time-space hierarchy between polynomial time and polynomial space
- Relativized logspace and generalized quantifiers over finite ordered structures
- scientific article; zbMATH DE number 2081098 (Why is no real title available?)
- scientific article; zbMATH DE number 3995053 (Why is no real title available?)
- Capturing complexity classes with Lindström quantifiers
- Term Rewriting and Applications
- Logics capturing relativized complexity classes uniformly
- Parameterised counting in logspace
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Parameterised counting in logspace
This page was built for publication: Relativized alternation and space-bounded computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111024)
