Strong Extension Axioms and Shelah’s Zero-One Law for Choiceless Polynomial Time

  • Andreas Blass ,
  • Yuri Gurevich

Journal of Symbolic Logic | , pp. 65-131

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.

[Choiceless Polynomial Time Computation and the Zero-One Law] is an abridged version of this paper, and [A New Zero-One Law and Strong Extension Axioms] is a popular version of this paper.