Deep Weisfeiler Leman
Deep Weisfeiler Leman
复制标题
深·维斯菲勒·莱曼
DOI：
10.1137/1.9781611976465.154
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
D. Wiebking
中科院分区：
文献类型：
--
作者：
M. Grohe;P. Schweitzer;D. Wiebking
我们介绍了Deep Weisfeiler Leman算法（DeepWL）的框架，它允许设计比著名的Weisfeiler-Leman算法更强大的纯组合图同构测试。我们证明，作为一个抽象的计算模型，多项式时间DeepWL-算法具有与逻辑Choiceless Polynomial Time完全相同的表达能力。（与计数）介绍了布拉斯，古列维奇，和谢拉（安纯应用逻辑，多项式时间图同构测试的存在是否意味着多项式时间规范化算法的存在，这是一个众所周知的开放问题。我们的主要技术结果指出，对于每一类图（满足一些温和的封闭条件），如果有一个多项式时间DeepWLisomorphism测试，那么有一个多项式时间的经典化算法，这类。这意味着在这个类上也有一个捕获多项式时间的逻辑。
We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm.We prove that, as an abstract computational model, polynomial-timeDeepWL-algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999).It is a well-known open question whether the existence of a polynomial-time graph isomorphism test implies the existence of a polynomial-time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomial-timeDeepWLisomorphism test, then there is a polynomial-time canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class.
登录
查看更多内容
影响因子：
4.3
作者：
Daniel Neuen;Pascal Schweitzer
通讯作者：
Pascal Schweitzer
DOI：
10.1137/1.9781611973402.120
发表时间：
2014-01
期刊：
--
影响因子：
--
作者：
R. O'Donnell;John Wright;Chenggang Wu;Yuan Zhou
通讯作者：
R. O'Donnell;John Wright;Chenggang Wu;Yuan Zhou
有界变量逻辑和计数：有限模型研究
DOI：
--
发表时间：
1997
期刊：
Lecture Notes in Logic
影响因子：
--
作者：
M. Otto
通讯作者：
M. Otto
作为复杂性衡量标准的表达性：结果和方向
DOI：
10.1109/psct.1987.10319271
发表时间：
1987
期刊：
Proceeding Structure in Complexity Theory
影响因子：
--
作者：
N. Immerman
通讯作者：
N. Immerman
DOI：
10.1007/3-540-56992-8_15
发表时间：
1992
期刊：
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
E. Grädel;M. Otto
通讯作者：
M. Otto