Locality from Circuit Lower Bounds
Locality from Circuit Lower Bounds
复制标题
电路下界的局部性
DOI：
10.1137/110856873
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Luc Segoufin
中科院分区：
文献类型：
--
作者：
Matthew Anderson;Dieter van Melkebeek;Nicole Schweikardt;Luc Segoufin
我们研究了一阶逻辑的扩展的局部性，它捕获了在${AC}^0}$中可计算的图查询，即多项式大小的等深度电路族。该扩展考虑关系结构上的一阶公式，这些关系结构可以使用任意数值谓词，其真值与数值谓词的特定解释无关。我们把这样的公式称为一阶不变公式。我们考虑了局部性的两个标准概念，Gaifman和Hanf局部性。我们的主要结果给出了一个Gaifman局部性定理：一个arb不变一阶公式不能区分两个在距离上具有相同邻域的元组，其中表示结构中元素的数量，并且是依赖于公式的常数。当将注意力限制在字符串结构上时，我们对汉夫局部性获得了相同的定量强度。在这两种情况下，我们都证明了边界是紧的。我们还介绍了我们的结果在正则语言研究中的应用。我们的证明利用了一阶公式与复杂度类${AC}^0}$之间的紧密联系，并依赖于恒深度电路上奇偶性的紧密下界。
We study the locality of an extension of first-order logic that captures graph queries computable in ${AC}^0}$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the particular interpretation of the numerical predicates. We refer to such formulas as Arb-invariant first-order. We consider the two standard notions of locality, Gaifman and Hanf locality. Our main result gives a Gaifman locality theorem: An Arb-invariant first-order formula cannot distinguish between two tuples that have the same neighborhood up to distance, whererepresents the number of elements in the structure andis a constant depending on the formula. When restricting attention to string structures, we achieve the same quantitative strength for Hanf locality. In both cases we show that our bounds are tight. We also present an application of our results to the study of regular languages. Our proof exploits the close connection between first-order formulas and the complexity class ${AC}^0}$ and hinges on the tight lower bounds for parity on constant-depth circuits.
登录
查看更多内容
词的因素
DOI：
--
发表时间：
1989
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
D. Beauquier;J. Pin
通讯作者：
J. Pin
Epsilon 逻辑在有限结构上比一阶逻辑更具表现力
影响因子：
0.6
作者：
M. Otto
通讯作者：
M. Otto
论赢得 Ehrenfeucht 游戏和 Monadic NP
影响因子：
0.6
作者：
T. Schwentick
通讯作者：
T. Schwentick
加法不变 FO 和正则性
DOI：
--
发表时间：
2010
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Nicole Schweikardt;L. Segoufin
通讯作者：
L. Segoufin
通过 Oracle 分离多项式时间层次结构（初步版本）
DOI：
--
发表时间：
1985
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
A. Yao
通讯作者：
A. Yao