Separating complexity classes related to \(\Omega\)-decision trees
type: Item
instance of: scholarly article
title: Separating complexity classes related to \(\Omega\)-decision trees
zbMATH Open document ID: 0848.68038
DOI: 10.1016/0304-3975(92)90257-G
author: Carsten Damm
author: Christoph Meinel
published in: Theoretical Computer Science
publication date: 1993-04-22T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 109480
MaRDI profile type: Publication
cites work: Q4726174
cites work: Q4385519
cites work: Bounded-depth, polynomial-size circuits for symmetric functions
cites work: Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
cites work: Q5567889
cites work: Polynomial size \(\Omega\)-branching programs and their computational power
cites work: Modified branching programs and their computational power
cites work: Lower bounds on monotone complexity of the logical permanent
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
cites work: On the complexity of branching programs and decision trees for clique functions
description: scientific article; zbMATH DE number 109480