Consistency in nondeterministic storage

DOI10.1016/0022-0000(84)90017-5zbMath0569.68040OpenAlexW1984654994MaRDI QIDQ1060847

Patrick W. Dymond, Walter J. Savitch

Publication date: 1984

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(84)90017-5

zbMATH Keywords

nondeterminismoraclecomplexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• Relationships between nondeterministic and deterministic tape complexities
• On relativizing auxiliary pushdown machines
• Relativization of questions about log space computability
• Log Space Recognition and Translation of Parenthesis Languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers