Choiceless Polynomial Time Computation and the Zero-One Law

This paper is a sequel to [Choiceless Polynomial Time], a commentary on [Saharon Shelah 634, “Choiceless polynomial time logic: inability to express”, these proceedings], and an abridged version of [Strong Extension Axioms and Shelah’s Zero-One Law for Choiceless Polynomial Time] that contains complete proofs of all the results presented here. The BGS model of computation was defined in [Choiceless Polynomial Time] with the intention of modeling computation with arbitrary finite relational structures as inputs, with essentially arbitrary data structures, with parallelism, but without arbitrary choices. It was shown that choiceless polynomial time, the complexity class defined by BGS programs subject to a polynomial time bound, does not contain the parity problem. Subsequently, Shelah proved a zero-one law for choiceless-polynomial-time properties. A crucial difference from the earlier results is this: Almost all finite structures have no non-trivial automorphisms, so symmetry considerations cannot be applied to them. Shelah’s proof therefore depends on a more subtle concept of partial symmetry.

After struggling for a while with Shelah’s proof, we worked out a presentation which we hope will be helpful for others interested in Shelah’s ideas. We also added some related results, indicating the need for certain aspects of the proof and clarifying some of the concepts involved in it. Unfortunately, this material is not yet fully written up. The part already written, however, exceeds the space available to us in the present volume. We therefore present here an abridged version of that paper and promise to make the complete version available soon.