Relativized alternation and space-bounded computation
From MaRDI portal
Recommendations
Cites work
- 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?)
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- A note on relativized log space
- A second step toward the polynomial hierarchy
- Alternating Pushdown and Stack Automata
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Computational Complexity of Probabilistic Turing Machines
- Limitations on Separating Nondeterministic Complexity Classes
- Log space machines with multiple oracle tapes
- On Approximation Algorithms for # P
- On Time Versus Space
- On bounded query machines
- On counting problems and the polynomial-time hierarchy
- On relativizing auxiliary pushdown machines
- 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 Questions Involving Probabilistic Algorithms
- Relativized polynomial hierarchies extending two levels
- 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
(17)- Computation by interaction for space-bounded functional programming
- Term Rewriting and Applications
- A survey of space complexity
- Capturing complexity classes with Lindström quantifiers
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- scientific article; zbMATH DE number 3995053 (Why is no real title available?)
- Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
- A time-space hierarchy between polynomial time and polynomial space
- Parameterised counting in logspace
- Nonerasing, counting, and majority over the linear time hierarchy
- A measure of relativized space which is faithful with respect to depth
- scientific article; zbMATH DE number 2081098 (Why is no real title available?)
- Space-efficient informational redundancy
- scientific article; zbMATH DE number 3940729 (Why is no real title available?)
- Relativized logspace and generalized quantifiers over finite ordered structures
- scientific article; zbMATH DE number 4092777 (Why is no real title available?)
- Logics capturing relativized complexity classes uniformly
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)
