Separating complexity classes related to \(\Omega\)-decision trees
From MaRDI portal
Publication:1202936
DOI10.1016/0304-3975(92)90257-GzbMath0848.68038MaRDI QIDQ1202936
Christoph Meinel, Carsten Damm
Publication date: 22 April 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial size \(\Omega\)-branching programs and their computational power
- Bounded-depth, polynomial-size circuits for symmetric functions
- Lower bounds on monotone complexity of the logical permanent
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Modified branching programs and their computational power
- Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
- On the complexity of branching programs and decision trees for clique functions
This page was built for publication: Separating complexity classes related to \(\Omega\)-decision trees
