The Setting
Choiceless polynomial time with counting (CPT), the model of Blass, Gurevich and Shelah, computes on a finite structure by building hereditarily finite sets over its elements, never choosing among them, within polynomially many steps and polynomially many active sets. A finite structure over a vocabulary of eight binary relations presents a system of linear equations over the field , a system that Gaussian elimination solves in polynomial time, and the Gauss query asks whether it has a solution.
Structures and the Gauss Query
The scalars are the elements of the field .β¦ The vocabulary consists of the binary relation symbols , , , , and one symbol for each scalar .β¦ A -structure on a finite set of atoms interprets each symbol of as a binary relation on .β¦ The configuration atoms of a -structure on form the set , its edge atoms the set β¦, and for we write .
A configuration atom and an edge atom are incident, written , when there are and with and .β¦ The edge coefficient of at is the scalar (1)β¦
Weights are normalized when they satisfy the first family of equations belowβ¦, and they are consistent with weights when the second family holds: (2)β¦ The Gauss query holds of , written , when the linear system (2) in the unknowns and has a solution.β¦
Hereditarily Finite Sets
The set of hereditarily finite sets over a set of atoms is the smallest set that contains every atom of , as an urelement with no elements, and every finite set of its own members.β¦ The rank of an atom and of the empty set is , and the rank of any other set is one more than the largest rank of its elements.β¦ The von Neumann ordinals are and β¦; the ordinal is the truth value standing for true.β¦ For finite , the set of all atoms has the atoms of as its elements.β¦
The transitive closure of and the closure of a finite family are the finite sets (3)
Machines and Their Runs
Fix a finite set of dynamic function symbols, each with an arity, and add the two control flags and , function symbols of arity . A location over is a symbol together with a tuple of members of whose length is the arity of .β¦ A state over assigns to every location a value in such that only finitely many locations, its support, carry a value other than .β¦ The critical sets of a state are the values and the arguments of the locations in its supportβ¦, and for finite its active sets form the finite set (4)β¦
Terms over and these symbols are variables, the ordinals , the set and applications ; from terms , and they further form the pair , the union , the unique element of , the cardinality , the tests , and β is an atomβ, the input relation for , negation, conjunction, the conditional choosing or according to , and the comprehension , which binds in its body and its guard .β¦ Rules are , updates , parallel compositions, conditionals, parallel loops and local definitions .β¦ An operational machine over consists of a finite set of dynamic function symbols with arities and one closed rule over them and the two flags, its body.β¦
On a -structure on a finite set , a store of is a state for its dynamic symbols and flagsβ¦, and the run of is the sequence of stores , each possibly undefined, where gives every location the value and arises from by one step of , which evaluates the body of in and applies the resulting updates, and is undefined when is or when these updates are inconsistent. A flag is raised in when gives it the value .β¦ The machine halts at step when is defined and is raised in it, and it accepts when for some both flags are raised in a defined .β¦ The active sets of the run through step are (5)β¦
For numbers and , the machine accepts within time and cumulative space , written , when for some both flags are raised in a defined and (6)β¦ and it accepts within time and space per state, written , when for some such (7)β¦ For polynomials and with natural coefficients, polynomial cumulative acceptance is β¦; for natural numbers and , cumulative cutoff acceptance and cutoff acceptance are and with .
A machine over is polynomially bounded when there are such that on every -structure on every finite set it halts at some step with (8)β¦
CPT Programs
A CPT program over consists of a finite set of dynamic function symbols with arities and a rule over them and the two flags, its body; its terms and rules are formed by the clauses above, with disjunction added to the Boolean connectives.β¦ Its stores, flags, run and active sets are defined as for machines. For polynomials and with natural coefficients, accepts within and when holds.β¦ A query on finite -structures is CPT-definable when some CPT program, with some polynomials and with natural coefficients, accepts within and exactly the structures that satisfy the query.β¦
The Claim
Theorem 1. Throughout, is a -structure on a finite set .
(a) The Gauss query is not CPT-definable: for every CPT program and all polynomials and with natural coefficients there is a structure with (9)β¦
(b) For every operational machine and all such polynomials and there is a structure with (10)β¦
(c) For every operational machine and all there is a structure with (11)β¦
(d) For every operational machine and all there is a structure with (12)β¦
(e) For every polynomially bounded operational machine there is a structure with (13)β¦
What Is Checked
The claims are stated over the Gauss query (2) on finite -structures with scalars in , over hereditarily finite sets and their closures (3), over the states, active sets (4) and runs (5) of operational machines and of CPT programs, and over the acceptance conditions (6) and (7), the polynomial bound (8) and CPT-definability.