Relativized alternation and space-bounded computation
From MaRDI portal
Publication:1111024
DOI10.1016/0022-0000(88)90034-7zbMath0657.68047OpenAlexW1978001037MaRDI QIDQ1111024
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90034-7
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (11)
Towards Computational Complexity Theory on Advanced Function Spaces in Analysis ⋮ A time-space hierarchy between polynomial time and polynomial space ⋮ Capturing complexity classes with Lindström quantifiers ⋮ Logics capturing relativized complexity classes uniformly ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Parameterised counting in logspace ⋮ Space-efficient informational redundancy ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ A survey of space complexity ⋮ Type-two polynomial-time and restricted lookahead ⋮ Nonerasing, counting, and majority over the linear time hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space-bounded hierarchies and probabilistic computations
- On bounded query machines
- Some results on relativized deterministic and nondeterministic time hierarchies
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On counting problems and the polynomial-time hierarchy
- Log space machines with multiple oracle tapes
- A second step toward the polynomial hierarchy
- Relationships between nondeterministic and deterministic tape complexities
- A note on relativized log space
- Parity, circuits, and the polynomial-time hierarchy
- Alternating Pushdown and Stack Automata
- Relativized polynomial hierarchies extending two levels
- On Approximation Algorithms for # P
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- On relativizing auxiliary pushdown machines
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Limitations on Separating Nondeterministic Complexity Classes
- Alternation
- Space-bounded simulation of multitape turing machines
- Relativized Questions Involving Probabilistic Algorithms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
- On Time Versus Space
- Computational Complexity of Probabilistic Turing Machines
- Oracles for Deterministic Versus Alternating Classes
- Parallel computation and the NC hierarchy relativized
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Relations Between Time and Tape Complexities
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Real-Time Simulation of Multihead Tape Units
This page was built for publication: Relativized alternation and space-bounded computation
