The Setting
Choiceless polynomial time with counting (CPT), in the style of Blass, Gurevich and Shelah, computes on a finite structure over a set of atoms by firing one rule again and again on a store of dynamic functions whose arguments and values are hereditarily finite objects over . A program accepts within polynomial bounds when it halts and accepts after polynomially many steps in , having made only polynomially many objects occur.✦
Three questions about a run up to a step bear on lower bounds for CPT on grid structures: how many objects the run touches, how small a support each of them has under a group acting on the atoms, and whether each dynamic function after steps is definable in a counting logic with few variables by one formula for all inputs at once. Here they are put to operational machines, which fire a closed rule and are watched by an observer term, and into which every program compiles.
Hereditarily Finite Objects and Supports
The hereditarily finite objects over a set of atoms form the least set that contains the atoms of , which have no elements, and every finite set of its members.✦ The von Neumann ordinals are , the empty set, and ✦, and the truth value stands for true.✦ When is finite, is the set of all atoms.✦ The closure of an object is the finite set .✦
Let a group act on , and through it on . A tuple of atoms supports an object if every that fixes each entry of fixes .✦ The object is -supported if some tuple of atoms supports it✦, and hereditarily -supported if every member of is -supported; is the set of hereditarily -supported objects.✦
Machines and Their Runs
Fix a vocabulary of binary relation symbols. An input over a finite set of atoms gives each a binary relation on .✦
A machine over consists of a finite set of dynamic function symbols, each with an arity, and a closed rule over , a rule in the sense defined below that has no free variables, whose function symbols are the dynamic ones and the two control flags and , of arity ✦; denotes the arity of a function symbol .✦
A location over is a function symbol with a tuple of arguments in .✦ A store of is a machine state for its function symbols✦: a map from locations to whose support, the set of locations at which is not , is finite.✦ A control flag holds in when .✦ The critical objects of are the arguments and the values at the locations of its support✦, and its active objects are (1)✦
The terms are the variables, the constants for , the term , the applications , and the terms built from smaller ones by pairing, union , the unique element, the cardinality , the tests , , is an atom and for , negation, conjunction, the conditional, and the comprehension , which binds in its guard and its body .✦
In a store , with values for its free variables, a term evaluates to an object of : a variable to its value, to the ordinal , to the set of all atoms, to the value of at and the values of the , a pairing, a union and the unique element to the pair, the union and the unique element of the values of its parts, to the ordinal of the number of elements of , a test, a negation and a conjunction to when it holds and to otherwise, a conditional to the value of its first or its second branch according as its condition is or not, and the comprehension to the set of values of at the elements of at which is .✦ The test holds when and are atoms related by ✦, and negation, conjunction and the conditional read as true and every other object as false.
The rules are , the update , the parallel composition , the conditional , the parallel loop and the local definition , the last two binding in ; a rule is closed when it has no free variables.✦
The initial state is the store that is at every location. One step of from a store performs the updates that prescribes in , and is defined when they are consistent. The run of on an input starts at , and is the store produced from by one step of , as long as each step is defined.✦ The active objects of the run of on up to step form the set , the union of the sets (1) of the defined stores with .✦ The evaluation trace of a term in a store , with values for its free variables, is the finite set of objects that occur while is evaluated in . The evaluation trace of a rule in collects those of its terms: the value and the arguments of an update, both parts of a parallel composition, the condition and both branches of a conditional, the bound of a loop with the body at every element of the bound, and the defining term of a local definition with the body at its value.✦ The run trace up to step is (2)✦
Each term has a bound , a polynomial in that bounds the size of its evaluation trace, and a width , both defined by recursion on . The bound of a rule is the polynomial with and (3)✦ and . The width of a rule is for and otherwise plus the widths of its terms and of its subrules.✦
Programs and Their Compiled Machines
A CPT program over consists of a finite set of dynamic function symbols, each with an arity, and a CPT rule, its body, over and the dynamic symbols together with and .✦ CPT terms and rules are built like those of a machine, with named variables for and with disjunction among the term constructions. The stores of are the machine states for its function symbols✦, with control flags read as for a machine✦; its run on an input starts at the initial state and applies one step of at a time, as long as the step is defined✦, and is the union of the active objects of .✦
The roots of a CPT term evaluated in a store, with values for its variables, form a finite set of objects, defined by recursion on the term. The roots of a CPT rule are those of the terms on the branches it executes: the value and the arguments of an update, both parts of a parallel composition, the condition of a conditional and the branch it selects, the bound of a loop with the body at every element of the bound, and the defining term of a local definition with the body at its value.✦ The roots of one step from are none when holds in , and otherwise the roots of the body with every variable set to .✦ The objects occurring up to step are (4)✦ the union running over the defined stores. For polynomials , accepts within , written , if for some the store is defined, and hold in it, and .✦
An observer of a machine is a closed term over its symbols, with value in a store .✦ The objects observed by in the run of on up to step form the set (5) and observed by accepts within , written , under the condition defining with (5) in place of (4).✦
The compiled machine of a program has the dynamic function symbols and arities of , and its rule is the body of translated construct by construct✦: a variable becomes a reference to the binder of that name around it, or the constant when there is none, and a disjunction of and becomes .✦ The collecting term of a CPT rule is defined by recursion on , merging the collecting terms of its terms with those of the subrules it executes, the body of a loop being collected at every element of the bound and that of a local definition at its value.✦ The root observer is the compiled form of , where is the body of .✦
The Grid Structures
The grid of side has vertex set ✦, edge set made of the unit segments along the three axes, each directed from its tail to its head, the endpoint with the larger coordinate✦, and face set made of the unit squares parallel to the three coordinate planes.✦ The edges at a vertex are those with as head or tail, and is if is the head of , if it is the tail, and otherwise.✦ The boundary map sends a chain to , where is the indicator vector of a vertex .✦ The central flow group is the kernel of , the space of flows, written multiplicatively.✦ The face cycle of a face goes once around its boundary, with value on its four sides and elsewhere.✦
For an edge , the faces on are the faces with .✦ The local group of is the central extension attached to the local cycle on the faces on ✦; its elements pair a labelling of the faces on by points of the plane with a flow in .✦ A local state at a vertex assigns an element to each edge at .✦ The local state is compatible when and have the same component at every face on both and ✦, and its divergence is the net flow into , where is the flow of .✦ For a charge , a configuration at is a compatible local state at with divergence .✦
The vocabulary has the eight binary symbols , , , , , , , .✦ The grid structure of a charge on the grid of side is the input over whose atoms are the edge atoms with and the configuration atoms with a configuration at for . In , holds between each edge atom and itself and between each configuration atom and itself, relates edge atoms on the same edge and configuration atoms at the same vertex, relates to the edge atom for every edge at , and, for , relates to when has flow .✦ The group acts on the atoms of : a flow moves an edge atom to and a configuration atom to with for every edge at .
Counting Logic and Uniform Definability
A binary relational structure with universe interprets each symbol of its vocabulary as a binary relation on .✦ For , the formulas of the counting logic with variables over that vocabulary are built from , the equations and the atoms between the variables by negation, conjunction, the quantifiers and the counting quantifiers for , where holds when exactly values of satisfy .✦ Free variables and satisfaction under an assignment of elements of to the variables are the usual ones.
Throughout, is a family of such structures over one vocabulary, the universe of being a set of hereditarily finite objects over a set of atoms . A family of relations is uniformly definable with variables if for every map there is one formula of , with free variables among , such that (6)✦ for every and every assignment of elements of to .
The Claim
Theorem 1. Let .
For every CPT program over , every input over a finite set of atoms and all polynomials , (7)✦
Let be a machine over and an input over a finite set of atoms , such that has at most active objects for every at which the run of on is defined. Then (8)✦
Let , , an integer and a real number, and let be a machine over such that has at most active objects for every at which the run of on is defined, and . Then, for the action of on the atoms of , (9)✦
Let be a machine over and, for each , let be an input over on which the run of is defined up to step , with stores . Suppose that , that for every function symbol of , and that for every and every each object of lies in and has at most elements. Then for every function symbol of the family (10)✦ is uniformly definable with variables.
Suppose that every is finite, that every contains the elements of its members and every ordinal , that the membership relation and the property of being a set are uniformly definable with variables, and that . Then the family (11)✦ is uniformly definable with variables.
Let with , and let the families and be uniformly definable with variables. Then so is the family of relations given, with all quantifiers over , by (12)✦
What Is Checked
The theorem is stated over operational machines with their stores, runs, active objects, evaluation traces, bounds and widths, over CPT programs with their occurring objects, compiled machines and root observers, over the grid structures with the action of on their atoms, and over uniform definability in for families of structures on hereditarily finite objects.