Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
复制标题
无选择多项式时间的强扩展公理和 Shelah 零一定律
DOI：
10.2178/jsl/1045861507
复制
发表时间：
2003
影响因子：
0.6
通讯作者：
Y. Gurevich
中科院分区：
文献类型：
--
作者：
A. Blass;Y. Gurevich
本文从Shelah对复杂性类“无选择多项式时间”的0 - 1定律的证明出发，定义了Shelah和作者。我们提出了一个详细的证明谢拉的结果图，并描述其推广到其他类型的结构的程度。扩张公理是早期0 - 1定律（一阶逻辑、定点逻辑和有限变量无穷逻辑）的基础，在无选择多项式时间的情况下是不适当的;它们必须被我们所说的强扩张公理所取代。我们提出了一个广泛的讨论，这些公理和它们的作用都在0 - 1定律和一般。
Abstract This paper developed from Shelah's proof of a zero-one law for the complexity class “choiceless polynomial time,” defined by Shelah and the authors. We present a detailed proof of Shelah's result for graphs, and describe the extent of its generalizability to other sorts of structures. The extension axioms, which form the basis for earlier zero-one laws (for first-order logic, fixed-point logic, and finite-variable infinitary logic) are inadequate in the case of choiceless polynomial time; they must be replaced by what we call the strong extension axioms. We present an extensive discussion of these axioms and their role both in the zero-one law and in general.