Separating Rank Logic from Polynomial Time
Separating Rank Logic from Polynomial Time
复制标题
将排序逻辑与多项式时间分离
DOI：
10.1109/lics52264.2021.9470598
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Moritz Lichter
中科院分区：
文献类型：
--
作者：
Moritz Lichter
在寻找捕捉多项式时间的逻辑时，最有希望的候选者是无选择多项式时间（CPT）和秩逻辑。秩逻辑扩展了不动点逻辑，在素域上通过秩运算符进行计数。证明了${{\mathbb{Z}}_{{2^i}$上的CFI图的同构问题不能用秩逻辑来定义，即使基图是全序的.然而，CPT可以定义这个同构问题。因此，我们从CPT中分离出秩逻辑，特别是从多项式时间中分离出来。
In the search for a logic capturing polynomial time the most promising candidates are Choiceless Polynomial Time (CPT) and rank logic. Rank logic extends fixed-point logic with counting by a rank operator over prime fields. We show that the isomorphism problem for CFI graphs over ${{\mathbb{Z}}_{{2^i}}}$ cannot be defined in rank logic, even if the base graph is totally ordered. However, CPT can define this isomorphism problem. We thereby separate rank logic from CPT and in particular from polynomial time.
登录
查看更多内容
线性丢番图方程、群 CSP 和图同构
DOI：
10.1137/1.9781611974782.21
发表时间：
2017
期刊：
影响因子：
--
作者：
C. Berkholz;M. Grohe
通讯作者：
M. Grohe
多项式时间是无选择的吗？
DOI：
10.1007/978-3-319-23534-9_11
发表时间：
2015
期刊：
影响因子：
--
作者：
E. Grädel;M. Grohe
通讯作者：
M. Grohe
DOI：
10.1109/lics.2019.8785682
发表时间：
2019
期刊：
2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
影响因子：
--
作者：
M. Grohe;D. Neuen
通讯作者：
D. Neuen
等级逻辑已死，等级逻辑万岁！
DOI：
10.1017/jsl.2018.33
发表时间：
2019
期刊：
The Journal of Symbolic Logic
影响因子：
--
作者：
Grädel;Wied Pakusa
通讯作者：
Wied Pakusa