Limitations on Separating Nondeterministic Complexity Classes

DOI10.1137/0210057zbMath0468.68052OpenAlexW1987444582MaRDI QIDQ3922171

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)

Related Items (7)

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

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