Separation of the Monotone NC Hierarchy
Separation of the Monotone NC Hierarchy
复制标题
单调 NC 层次结构的分离
DOI：
10.1109/sfcs.1997.646112
复制
发表时间：
1997
期刊：
影响因子：
1.1
通讯作者：
P. McKenzie
中科院分区：
文献类型：
--
作者：
R. Raz;P. McKenzie
，对于函数在单调-P中的单调深度。结果，我们实现了以下类的分离。
1. Monotone-NC≠Monotone-P.
2.对每个i ≥1，Monotone-≠Monotone-.
3.更一般的 ：对于任意整数函数D(N)，直到(对于某些ε>；0)，我们给出了一个单调布尔函数的显式例子，它可以由深度为D(N)的多项式大小的单调布尔电路计算，但不能由深度小于const·D(N)(对于某个常量)的任何(扇入2)单调布尔电路计算。我们的论点更具一般性：我们定义了一类新的通信复杂性搜索问题，以下称为DART对策，并证明了这类问题中每个成员的通信复杂性的一个紧下界。作为结果，我们得到了许多函数单调深度的下界。具体地说，我们得到以下界限：
1. 对于st-连通性，我们得到了的一个紧下界。也就是说，我们得到了Karchmer-Wigderson定理的一个新的证明，作为我们一般结果的直接推论。
2.对于k-团函数，我们得到了 (Klogn)的一个紧下界。这个下界以前是已知的，对于k≤n[1]。然而，对于较大的k，以前只知道Ω(K)的界。
, 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.