Equivalence in Finite-Variable Logics is Complete for Polynomial Time
Equivalence in Finite-Variable Logics is Complete for Polynomial Time
复制标题
有限变量逻辑中的等价性对于多项式时间是完全的
DOI：
10.1109/sfcs.1996.548485
复制
发表时间：
1996
期刊：
影响因子：
1.1
通讯作者：
Martin Grohe
中科院分区：
文献类型：
--
作者：
Martin Grohe
一阶逻辑，其公式最多包含k个变量（对于某些）。我们表明，对于每一个，等价的逻辑是完整的多项式时间。此外，我们证明了同样的完备性结果也适用于具有计数量词的强有力的扩展（对于每一个）. k维Weisfeiler-Lehman算法是一种组合的方法来图同构，推广了朴素的颜色细化方法（对于）. Cai，Fürer和Immerman [6]证明了两个有限图在逻辑上是等价的当且仅当它们可以用k维Weisfeiler-Lehman算法区分。因此，我们的主要结果的一个推论是，两个有限图是否可以区分的k维Weisfeiler-Lehman算法的问题是P-完全的。
of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ).The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each .