Article contents
Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits
Published online by Cambridge University Press: 15 April 2002
Abstract
The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2001
References
- 6
- Cited by