Strong extension axioms and Shelah's zero-one law for choiceless polynomial time

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.