Separation of the monotone NC hierarchy
type: Item
instance of: scholarly article
title: Separation of the monotone NC hierarchy
zbMATH Open document ID: 0977.68037
author: Ran Raz
author: Pierre McKenzie
published in: Combinatorica
publication date: 2000-05-14T00:00:00Z
review text: The class monotone-\(NC^i\) is the class of all functions that can be computed by polynomial-size circuits of depth \(O(\log^in)\) over the monotone base \(\{\wedge,\vee\}\). It is shown that, for all \(i\), monotone-\(NC^i\) is a strict subclass of monotone-\(NC^{i+1}\), and, thus, monotone-\(NC\), the union of the classes monotone-\(NC^i\) over all \(i\), is a strict subclass of monotone-\(P\). This substantially improves the only previously known separation of monotone-\(NC^1\) from monotone-\(NC^2\). Additionally, more general results, for arbitrary bounds \(D(n)\) below \(n^\varepsilon\), are obtained. Further consequences address the complexity of two particular problems: st-connectivity and \(k\)-clique. The proof of the main result relies on a communication theoretic argument, for which a new class of games, so called DART games, are introduced.
reviewed by: Heribert Vollmer
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1446738
zbMATH Keywords: monotone circuits
zbMATH Keywords: monotone-NC
zbMATH Keywords: communication complexity
MaRDI profile type: Publication
full work available at URL: s004930050062
OpenAlex ID: W3022335368
Wikidata QID: Q30054697
DOI: 10.1007/S004930050062
Recommended article: Q4895289
Recommended article: Q4714240
Recommended article: Separation of NP-completeness notions
Recommended article: Nondeterministic Separations
Recommended article: Monotone separations for constant degree polynomials
Recommended article: Hierarchies in Fragments of Monadic Strict NP
Recommended article: The Complexity of Separation for Levels in Concatenation Hierarchies
Recommended article: Monotonicity and separation for the Mumford-Shah problem
Recommended article: Separation of deterministic, nondeterministic and alternating complexity classes
Recommended article: Strongly Exponential Separation between Monotone VP and Monotone VNP
description: scientific article; zbMATH DE number 1446738