Relativized alternation and space-bounded computation
type: Item
instance of: scholarly article
title: Relativized alternation and space-bounded computation
zbMATH Open document ID: 0657.68047
DOI: 10.1016/0022-0000(88)90034-7
author: Jonathan F. Buss
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4074485
zbMATH Keywords: oracles
zbMATH Keywords: alternating Turing machines
zbMATH Keywords: relativizations
MaRDI profile type: Publication
full work available at URL: 0022-0000(88)90034-7
OpenAlex ID: W1978001037
cites work: Space-bounded simulation of multitape turing machines
cites work: On relativizing auxiliary pushdown machines
cites work: On counting problems and the polynomial-time hierarchy
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: A second step toward the polynomial hierarchy
cites work: On bounded query machines
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: Q4721649
cites work: Alternation
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Q5666536
cites work: Real-Time Simulation of Multihead Tape Units
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Oracles for Deterministic Versus Alternating Classes
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Relativized polynomial hierarchies extending two levels
cites work: On Time Versus Space
cites work: Relations Between Time and Tape Complexities
cites work: Q5592246
cites work: Q3912025
cites work: Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
cites work: Alternating Pushdown and Stack Automata
cites work: Relativization of questions about log space computability
cites work: Log space machines with multiple oracle tapes
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Some results on relativized deterministic and nondeterministic time hierarchies
cites work: Q3670562
cites work: Relativized Questions Involving Probabilistic Algorithms
cites work: Limitations on Separating Nondeterministic Complexity Classes
cites work: Space-bounded hierarchies and probabilistic computations
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: A note on relativized log space
cites work: On Approximation Algorithms for # P
cites work: A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
cites work: Q4720786
cites work: Parallel computation and the NC hierarchy relativized
description: scientific article; zbMATH DE number 4074485