Separation of the Monotone NC Hierarchy |
| |
Authors: | Ran Raz Pierre McKenzie |
| |
Institution: | (1) Department of Applied Mathematics and Computer Science, Weizmann Institute; Rehovot, 76100 Israel; E-mail: ranraz@wisdom.weizmann.ac.il, IL;(2) Département d'informatique et recherche opérationnelle, Université de Montréal; C.P. 6128, succursale Centre-ville, Montréal (Québec), H3C 3J7 Canada; E-mail: mckenzie@iro.umontreal.ca, CA |
| |
Abstract: | , for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes.
1. monotone-NC ≠ monotone-P.
2. For every i≥1, monotone-≠ monotone-.
3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone
Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const).
Only a separation of monotone- from monotone- was previously known.
Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART
games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get
lower bounds for the monotone depth of many functions. In particular, we get the following bounds:
1. For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result.
2. For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n 1]. For larger k, however, only a bound of Ω(k) was previously known.
Received: December 19, 1997 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 68Q15 68Q25 68R99 |
本文献已被 SpringerLink 等数据库收录! |
|