Formulas vs. circuits for small distance connectivity
Formulas vs. circuits for small distance connectivity
复制标题
短距离连接的公式与电路
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Benjamin Rossman
中科院分区：
文献类型：
--
作者：
Benjamin Rossman
我们给出了有界深度布尔公式与电路能力上的首个超多项式分离。具体而言，我们考虑距离$k(n)$连通性问题，该问题询问在一个大小为$n$的图中两个指定节点是否由一条长度至多为$k(n)$的路径相连。这个问题在深度为$O(\log k)$且大小为$O(kn^3)$的电路上可解（通过递归加倍技术）。相比之下，我们表明对于所有$k(n)\leq\log\log n$，在深度为$\log n/(\log\log n)^{O(1)}$的公式上解决这个问题需要大小为$n^{\Omega(\log k)}$。作为推论：（i）由此可知，对于所有$k(n)\leq\log\log n$，距离$k(n)$连通性的多项式大小电路需要深度为$\Omega(\log k)$。这与递归加倍的上界相匹配，并改进了比姆（Beame）、因帕利亚佐（Impagliazzo）和皮塔西（Pitassi）[BIP98]之前的$\Omega(\log\log k)$下界。（ii）对于所有$s(n)=n^{O(1)}$且$d(n)\leq\log\log\log n$，我们得到了用深度为$d$的公式模拟大小为$s$深度为$d$的电路所需大小的紧下界为$s^{\Omega(d)}$。对于任何$d(n)\nless O(1)$，之前已知的下界都不优于$s^{\Omega(1)}$。我们的证明技术基于一种新的路径集复杂度概念，大致来说，它衡量在满足一定密度约束的情况下，通过并集和关系连接操作在大小为$n$的全集内构建一组（部分）路径的最小成本。我们证明的一半表明解决距离$k(n)$连通性的有界深度公式意味着路径集复杂度的上界。另一半是路径集复杂度的组合下界。
We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance k(n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a path of length at most k(n). This problem is solvable (by the recursive doubling technique) on circuits of depth O(log k) and size O(kn3). In contrast, we show that solving this problem on formulas of depth log n/(log log n)O(1) requires size nΩ(log k) for all k(n) ≤ log log n. As corollaries: (i) It follows that polynomial-size circuits for Distance k(n) Connectivity require depth Ω(log k) for all k(n) ≤ log log n. This matches the upper bound from recursive doubling and improves a previous Ω(log log k) lower bound of Beame, Impagliazzo and Pitassi [BIP98]. (ii) We get a tight lower bound of sΩ(d) on the size required to simulate size-s depth-d circuits by depth-d formulas for all s(n) = nO(1) and d(n) ≤ log log log n. No lower bound better than sΩ(1) was previously known for any d(n) ≮ O(1). Our proof technique is centered on a new notion of pathset complexity, which roughly speaking measures the minimum cost of constructing a set of (partial) paths in a universe of size n via the operations of union and relational join, subject to certain density constraints. Half of our proof shows that bounded-depth formulas solving Distance k(n) Connectivity imply upper bounds on pathset complexity. The other half is a combinatorial lower bound on pathset complexity.