Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T10:22:22.214Z Has data issue: false hasContentIssue false

Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits

Published online by Cambridge University Press:  15 April 2002

Jan Johannsen*
Affiliation:
Institut für Informatik, Ludwig-Maximilians-Universität München, Oettingenstraße 67, 80538 München, Germany; e-mail: jjohanns@informatik.uni-muenchen.de
Get access

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.

Information

Type
Research Article
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable