Separating complexity classes related to bounded alternating ?-branching programs

DOI10.1007/BF01294594zbMath0830.68048OpenAlexW2012779543MaRDI QIDQ4327378

Stephan Waack, Christoph Meinel

Publication date: 5 April 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294594

zbMATH Keywords

branching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Meanders and their applications in lower bounds arguments
• Relationships between nondeterministic and deterministic tape complexities
• On the complexity of branching programs and decision trees for clique functions
• Structure and importance of logspace-MOD class
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

This page was built for publication: Separating complexity classes related to bounded alternating ?-branching programs