The Setting
Choiceless polynomial time with counting (CPT) computes on a finite structure by building hereditarily finite sets over its elements, without arbitrary choices, within polynomial bounds on its steps and on the sets it builds. Theorem 1 says that CPT does not capture polynomial time, and the query that separates the two is : on a structure over a vocabulary of eight binary relations, asks whether a system of linear equations over read off the structure has a solution. The inputs compared are the grid structures and of two charges and , which assign an element of to each vertex of a cubic grid of side and differ at a single vertex.
Interpretation programs iterate a logical interpretation in first-order logic with the Härtig quantifier; choiceless machines, in the style of Blass, Gurevich and Shelah, run a rule on hereditarily finite sets.
The Query
The vocabulary consists of the binary symbols , , , , and for .✦ An input structure on a finite set interprets each symbol of as a binary relation on .✦ The edge atoms of form the set , its configuration atoms the set ✦, and for a configuration atom we put . A configuration atom and an edge atom are incident when there are and with and .✦ The edge coefficient of at is the sum, over the edge atoms with , of the scalars with .✦
Weights are normalized, and weights are consistent with them, when (1) The query holds of when there are normalized weights and weights consistent with them.✦
The Grid Structures
The grid of side has the vertex set .✦ The edges of the grid are the unit segments parallel to the axes: the edge along has tail and head , and the edges and along and run from to and to ; is the set of all of them. A vertex is incident to an edge when it is the head or the tail of ✦, and the orientation sign is if is the head of , if it is the tail and otherwise✦. The faces are the unit squares parallel to the , and planes, each given by its lowest corner, and is the set of them.✦ The face cycle of a face goes once around its boundary; for the face in the plane with lowest corner it is (2)✦ and the faces in the other two planes are traversed in the same way.
For a set of faces, a group whose elements are called flows and a map , the support group is the central extension, attached to , of the group of face labellings by ; its elements are the pairs of a face labelling and a flow.✦ The faces on an edge form the set of squares with as a side✦, and the local cycle of sends to ✦. The local group of is the support group of its local cycle, with flows in .✦
A local state at a vertex assigns to each edge at an element of ✦; it is compatible when, for any two edges and at and any face on both, and have the same component at .✦ The divergence of a local state at is the net flow into , where the flow of an element of is its second component, (3) For a charge , a configuration at is a compatible local state at of divergence .✦
The atoms of are of two disjoint sorts: the edge atoms with , and the configuration atoms with a configuration at .✦ The grid structure is the structure over whose universe is the set of atoms of and whose relations hold exactly as follows: relates each edge atom to itself and each configuration atom to itself; relates any two edge atoms over the same edge, and any two configuration atoms over the same vertex; relates to for every edge at ; and relates to when has flow . The two charges, defined for a vertex of the grid, are and , equal to at and to elsewhere.✦
Interpretation Programs
A finite structure over a set of binary relation symbols is a finite universe with a binary relation on it for each .✦ The formulas of first-order logic with the Härtig quantifier, , over in variables are built from , and by negation, conjunction, and , the two quantifiers binding a new variable .✦ Satisfaction is defined by recursion, with true when as many elements satisfy as satisfy , and a sentence holds in , written , when the empty assignment satisfies it.✦ The scoped width of a formula is the largest number of variables in scope at any of its atomic subformulas.✦
A two-dimensional interpretation of structures over in structures over consists of formulas over : a domain formula in two variables, an equivalence formula in four, and for each symbol of a relation formula in four.✦ The interpretation sends a finite structure over to the structure over whose elements are the pairs of elements of satisfying the domain formula, identified when they satisfy the equivalence formula, and whose relations are given by the relation formulas. An interpretation program over consists of a finite vocabulary of state symbols, an initial interpretation of structures over in structures over , a step interpretation of structures over in structures over , and two sentences over , the halting condition and the output condition .✦ The states of on a finite structure over are and .✦
A step is the first halting step of on when and for every ✦, and accepts when it has a first halting step with .✦ The cost of on up to step counts the states and their elements, (4)✦ and is polynomially bounded when there are natural numbers and such that on every finite structure over it has a first halting step with .✦
Choiceless Machines
The hereditarily finite objects over a set of atoms are the atoms, which have no elements, and the finite sets of such objects, two sets being equal when they have the same elements.✦ The rank of an object is for an atom and for the empty set, and otherwise one more than the largest rank of its elements.✦ The transitive closure of an object is ✦, and the closure of a finite family of objects is the union of the transitive closures of its members.✦ The von Neumann ordinals are and ✦; the empty set stands for false✦ and for true✦, and is the set of all atoms of .✦
A choiceless machine over a vocabulary consists of a finite set of dynamic function symbols, each with an arity, and a rule (defined below) without free variables, written in these symbols, the input relations of and two nullary control flags, and .✦ A machine state assigns an object of to every dynamic function symbol applied to a tuple of objects of the length of its arity, all but finitely many of these values being the empty set; terms in free variables, and their values in under an assignment of objects to the variables, are given by recursion.✦ A variable takes its assigned value, the constant the ordinal , the set of all atoms, and the value of at and the values of . The pair , the union , the unique element of and the cardinality of are formed from the values. The tests , , “ is an atom” and for , the negation and the conjunction take the value when they hold and otherwise, a term counting as true when its value is . The conditional takes the value of when is true and that of otherwise, and the comprehension of two terms and , in which is bound, is the set of the values of for the elements of at which is true.
The rules over these terms are , the update , the parallel composition of two rules, the conditional rule , and the rules and , which bind .✦
A location is a function symbol together with a tuple of objects whose length is the arity of .✦ The states of are the machine states on the locations of its function symbols and its flags.✦ The support of is the finite set of locations with a nonempty value✦, and its critical sets are the values and the arguments at these locations✦. The active sets form the closure of the family made of the critical sets, , , and the atoms of .✦ A flag holds in when its value there is .✦ One step of the rule in a state evaluates the rule in , which yields updates of locations, and applies these updates to . On an input structure on , the run of is the sequence of states that starts from the initial state, in which every location holds the empty set, and passes to the next state by one step of the rule, for as long as that step is defined.✦
An observer of is a term without free variables in the symbols of , with value in a state .✦ The observed sets up to step are (5)✦ the unions running over the steps the run reaches. For polynomials and with natural coefficients and an input structure on a finite set , accepts with observer in time and space , written , when the run on reaches, at some step , a state in which both and hold, and .✦
Numeric Bounds
For natural numbers and , the time exponent is ✦ and the trace exponent is ✦. The palette size of a real number is ✦, and for reals and the radius is ✦. For a grid side , a number of atoms and a trace exponent , the box radius is , the radius with . The box constant is .✦ A grid side and a number of variables satisfy the giant component bound when .✦ The local size bound is ✦, and the atom size constant is ✦.
The Claim
Theorem 1. (a) Let and be natural numbers with time exponent and trace exponent , and let be a natural number. Then (6)✦
(b) Let , and be reals and a natural number. For every sufficiently large real , the radius and the palette size satisfy (7)✦
(c) Let and be natural numbers. There is a grid side such that, with the bound on its number of atoms, its palette size and the box radius, the numbers and satisfy the giant component bound and (8)✦
(d) Let be an interpretation program over , let be a grid side with a vertex , and let , , , and satisfy the giant component bound and the conditions (8). Then for every step less than a step bound , a natural number fixed by the data of the hypotheses, and every sentence of over the state symbols of of scoped width less than , (9)✦
(e) Let be an interpretation program over with first halting steps on a finite structure and on a finite structure , and suppose that at every step the states and agree on and on . Then (10)✦
(f) Let be a polynomially bounded interpretation program over . There are a grid side and a vertex with (11)✦
(g) Let be a choiceless machine over with an observer , and let and be polynomials with natural coefficients. There are a grid side and a vertex with (12)✦
(h) Under the hypotheses of (g), there is an input structure on a finite set with (13)✦
What Is Checked
The claims are stated over the grid structures and with their atoms, local groups and configurations, over the query , over interpretation programs in with their states, first halting steps, acceptance and cost, over choiceless machines on with an observer and their observed sets, and over the time and trace exponents, the radius, the palette size and the giant component bound.