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.
翻译:在寻找掌握多元时间的逻辑时,最有前途的候选人是无选择的多元时间(CPT)和级级逻辑。 Rian逻辑将固定点逻辑延伸至由一个级操作员对黄金田进行计数。我们显示,即使基本图表完全按顺序排列,CFI图表的等值逻辑也无法界定CFI图表的等式问题。然而,CPT可以定义这个无形态问题。我们因此将等级逻辑与CPT,特别是多元时间区分开来。