On bounded query machines
type: Item
instance of: scholarly article
title: On bounded query machines
zbMATH Open document ID: 0608.68038
DOI: 10.1016/0304-3975(85)90168-9
author: Ronald V. Book
author: José L. Balcázar
author: Uwe Schöning
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: Simple proofs are given for each of the following results: (a) \(P=PSPACE\) if and only if, for every set A, \(P(A)=PQUERY(A)\) \textit{[A. L. Selman}, \textit{Xu Mei-Rui} and \textit{R. V. Book}, SIAM J. Comput. 12, 565-579 (1983; Zbl 0551.68043)]; (b) \(NP=PSPACE\) if and only if, for every set A, \(NP(A)=NPQUERY(S)\) [\textit{R. V. Book}, Theor. Comput. Sci. 15, 27-39 (1981; Zbl 0473.68039)]; (c) \(PH=PSPACE\) if and only if, for every set A, \(PH(A)=PQH(A)\) [\textit{R. V. Book} and \textit{C. Wrathall}, ibid. 15, 41-50 (1981; Zbl 0473.68040)]; (d) \(PH=PSPACE\) if and only if, for every sparse set S, \(PH(S)=PQH(S)=PSPACE(S)\) [the authors, ''The polynomial-time hierarchy and sparse oracles'', J. Assoc. Comput. Mach. (to appear); \textit{T. Long} and \textit{A. Selman}, ''Relativizing complexity classes with sparse oracles'', ibid. (to appear)].
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3984576
zbMATH Keywords: polynomial-time hierarchy
zbMATH Keywords: relativization
zbMATH Keywords: complexity classes
zbMATH Keywords: sparse oracles
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90168-9
OpenAlex ID: W1992440350
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Bounded query machines: on NP and PSPACE
cites work: Quantitative Relativizations of Complexity Classes
cites work: Bounded query machines: on NP( ) and NPQUERY( )
cites work: On the random oracle hypothesis
cites work: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Positive Relativizations of Complexity Classes
cites work: The polynomial-time hierarchy
cites work: Complete sets and the polynomial-time hierarchy
description: scientific article; zbMATH DE number 3984576