AbstractThis 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.
这篇论文的动机是探讨是否存在一种逻辑能够捕捉无序结构上的多项式时间计算。我们考虑了在已知的逻辑定义的多项式时间复杂度类边界附近的几个算法问题。我们展示了固定点逻辑加计数比预期更强大,因为它可以表达二部图中完全匹配的存在。我们重新审视了将多项式时间与固定点加计数分开的已知示例。我们展示了蔡、弗勒和伊默曼的一篇论文中的示例,在适当填充的情况下,处于无选择多项式时间,但不在固定点加计数中。没有填充的情况下,它们仍然在多项式时间中,但似乎不在无选择多项式时间加计数中。对于古列维奇和谢拉的多足动物示例,类似的结果成立,除了他们的多足动物的最终版本在某种意义上已经适当填充。最后,我们描述了另一个可能的候选者,涉及行列式,用于将多项式时间与无选择多项式时间加计数分开的任务。