Bounded query machines: on NP and PSPACE
type: Item
instance of: scholarly article
title: Bounded query machines: on NP and PSPACE
zbMATH Open document ID: 0473.68039
DOI: 10.1016/0304-3975(81)90061-X
author: Ronald V. Book
published in: Theoretical Computer Science
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3742621
zbMATH Keywords: languages accepted by nondeterministic polynomial space-bounded oracle machines
zbMATH Keywords: languages accepted by deterministic polynomial space-bounded oracle machines
MaRDI profile type: Publication
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: A second step toward the polynomial hierarchy
cites work: On Languages Accepted in Polynomial Time
cites work: Polynomial Space and Transitive Closure
cites work: On languages accepted by space-bounded oracle machines
cites work: On languages specified by relative acceptance
cites work: Bounded query machines: on NP( ) and NPQUERY( )
cites work: A hierarchy for nondeterministic time complexity
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Separating Nondeterministic Time Complexity Classes
cites work: The lattices of prefixes and overlaps of traces
cites work: Rudimentary Predicates and Relative Computation
cites work: Time- and tape-bounded Turing acceptors and AFLs
full work available at URL: 0304-3975(81)90061-x
OpenAlex ID: W1973386461
description: scientific article; zbMATH DE number 3742621