Choiceless Polynomial Time on Structures with Small Abelian Colour Classes
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes
复制标题
小阿贝尔色类结构的无选择多项式时间
DOI：
10.1007/978-3-662-44522-8_5
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Wied Pakusa
中科院分区：
文献类型：
--
作者：
Faried Abu Zaid;E. Grädel;Martin Grohe;Wied Pakusa
无选择多项式时间（CPT）是寻求多项式时间逻辑的候选者之一。它是计数定点逻辑（FPC）的严格扩展，但迄今为止还不知道它是否表达了有限结构的所有多项式时间性质。我们研究了有界色类大小为q的关系结构（简称q-有界结构）的同构问题的CPT-可定义性。我们的主要结果给出了一个积极的答案，甚至CPT-可定义的规范化程序，类的q-有界结构与小阿贝尔群的颜色类。这类具有阿贝尔颜色的q-有界结构自然出现在许多情况下。例如，2-有界结构具有阿贝尔颜色，这表明CPT捕获2-有界结构上的Ptime。特别是，这表明，多足类的同构问题是可定义的CPT，一个开放的问题所提出的布拉斯，古列维奇和谢拉。
Choiceless Polynomial Time (CPT) is one of the candidates in the quest for a logic for polynomial time. It is a strict extension of fixed-point logic with counting (FPC) but to date it is unknown whether it expresses all polynomial-time properties of finite structures. We study the CPT-definability of the isomorphism problem for relational structures of bounded colour class size q (for short, q-bounded structures). Our main result gives a positive answer, and even CPT-definable canonisation procedures, for classes of q-bounded structures with small Abelian groups on the colour classes. Such classes of q-bounded structures with Abelian colours naturally arise in many contexts. For instance, 2-bounded structures have Abelian colours which shows that CPT captures Ptime on 2-bounded structures. In particular, this shows that the isomorphism problem of multipedes is definable in CPT, an open question posed by Blass, Gurevich, and Shelah.
带计数的定点逻辑中的最大匹配和线性规划
DOI：
10.1109/lics.2013.23
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Anderson M
通讯作者：
Anderson M