Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract)
Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract)
复制标题
无选择多项式时间、计数和 Cai-Fürer-Immerman 图：（扩展摘要）
DOI：
10.1016/j.apal.2007.11.011
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Benjamin Rossman
中科院分区：
文献类型：
--
作者：
A. Dawar;David Richerby;Benjamin Rossman
我们考虑了由Blass，Gurevich和̃提出的无选择多项式时间语言(C IFP PT)，并证明了它可以表达由Cai，Fürer和Immerman最初构造的一个查询，以将带计数的定点逻辑(IFP+C)从P中分离出来，解决了Blass等人提出的一个问题.我们提出的程序使用无界有限秩集：我们通过证明查询不能被任何在所用集秩界上具有常量界的程序来计算，即使在C̃PT(卡片)中也是如此，C̃PT(卡片)是带计数的C CMPT的扩展。
We consider Choiceless Polynomial Time (C̃PT), a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting (IFP + C) from P. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank of sets used, even in C̃PT(Card), an extension of C̃PT with counting.