Limitations on Separating Nondeterministic Complexity Classes

DOI10.1137/0210057MaRDI QIDQ3922171zbMATH OpenOpenAlexFDO

Authors Joel I. Seiferas, Charles W. Rackoff

Publication date 1981

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0210057

zbMATH Keywords

time complexitynondeterministic computationrelativized computationcomplexity hierarchiesquery machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(7)

• A measure of relativized space which is faithful with respect to depth
• Relativized alternation and space-bounded computation
• New developments in structural complexity theory
• Downward translations of equality
• A survey of space complexity
• Almost-everywhere complexity hierarchies for nondeterministic time
• RelativizedNC

This page was built for publication: Limitations on Separating Nondeterministic Complexity Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922171)