Census techniques collapse space classes

DOI10.1016/0020-0190(94)00059-XzbMath0942.68570OpenAlexW2080371886MaRDI QIDQ1332770

Edith Hemaspaandra

Publication date: 14 August 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00059-x

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• The strong exponential hierarchy collapses
• The method of forced enumeration for nondeterministic automata
• Relationships between nondeterministic and deterministic tape complexities
• Relativized polynomial hierarchies extending two levels
• Nondeterministic Space is Closed under Complementation
• Relativization of questions about log space computability