On polynomial time computation over unordered structures
On polynomial time computation over unordered structures
复制标题
无序结构的多项式时间计算
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
S. Shelah
中科院分区：
文献类型：
--
作者：
A. Blass;Y. Gurevich;S. Shelah
摘要本文研究了无序结构上是否存在一种逻辑捕获多项式时间计算的问题。我们考虑几个算法问题的边界附近的已知的，逻辑上定义的复杂性类包含在多项式时间。我们表明，不动点逻辑加上计数是强于预期的，因为它可以表示存在一个完全匹配的二分图。我们重新审视已知的例子，从固定点加计数分离多项式时间。我们表明，蔡，Fürer和Immerman的文件中的例子，适当填充时，在无选择的多项式时间，但不是在不动点加计数。如果没有填充，它们仍然处于多项式时间，但似乎不是处于无选择的多项式时间加计数。类似的结果也适用于古列维奇和希拉的多足动物例子，只是他们的多足动物的最终版本在某种意义上已经被适当地填充了。最后，我们描述了另一种可能的候选人，涉及决定因素，从选择多项式时间加上计数的任务分离多项式时间。
Abstract This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting.