The Setting
Choiceless polynomial time with counting (CPT), the logic of Blass, Gurevich and Shelah, computes on a finite structure by building hereditarily finite sets over its elements, in parallel and without choosing among them, under polynomial bounds on the number of steps and on the number of objects that occur in the run. The question is whether CPT defines every isomorphism-invariant query that is decidable in polynomial time.
Theorem 1 answers it with an explicit query from linear algebra over , posed on finite structures for the vocabulary of eight binary relation symbols, one for each . Besides CPT programs, it concerns interpretation programs, which iterate a two-dimensional interpretation in first-order logic with the HΓ€rtig quantifier under a polynomial bound.
Inputs and the Query
An input over a finite set is a -structure with universe , that is, a binary relation for each ; the elements of are its atoms.β¦ An isomorphism from an input over to an input over is a bijection with for all and , and when there is one.β¦
The edge atoms of form the set β¦ and its configuration atoms the set β¦; the block of is . A configuration atom and an edge atom are incident when and hold for some and some .β¦ The coefficient of a configuration atom at an edge atom is the element (1)β¦ of .
A weighting is normalized when (2)β¦ and a labelling is consistent with when, with the coefficients (1), (3)β¦ The separating query holds of when the linear system (2), (3) in the unknowns for and for has a solution over .β¦
Polynomial Time
An ordered input of size is an input over .β¦ The ordered copy of an input over along a bijection is the ordered input with for every .β¦
Write for . The table of an ordered input of size is the string of its bits for and , in lexicographic order of .β¦ The tape code of an ordered input of size is the word over the alphabet made of blanks , the letter , and the table of with each bit written as the letter or .β¦ A Boolean answer is written as the one letter or .β¦
The query is decided in polynomial time, written , when there are a Boolean function on ordered inputs of all sizes and a Turing machine with finitely many stacks over finite alphabets that computes , from tape codes to answers, in time polynomial in the length of the tape code, such that (4)β¦ for every input over a finite set and every bijection of with some .
Hereditarily Finite Sets
For a finite set of atoms, is the set of hereditarily finite objects over : the least set that contains the atoms and every finite subset of itself, an atom having no elements.β¦ The rank of an object is when is an atom or , and otherwise.β¦ The transitive closure of an object is the finite set (5)β¦ and that of a finite set of objects is .β¦ The von Neumann ordinals are and β¦, the truth value is β¦, and the set of all atoms is itself an object of .β¦
CPT Programs
A CPT program over consists of a finite set of dynamic function symbols, each with an arity, and one rule, its body, over these symbols and the two nullary control symbols and .β¦ The terms of are built from variables, the ordinals and the set of atoms by application of a symbol of arity , pairing, union, the unique-element operation, cardinality, equality, membership, the atom test, the input relations for , negation, conjunction, disjunction, conditional terms and comprehension terms , where is a variable and , , , are terms.β¦ The rules of are built from and updates by parallel composition, conditional rules, parallel iteration and local definitions .
On an input over , a location is a symbol of arity , dynamic or control, with an argument tuple in β¦, and a state assigns to every location a value in , all but finitely many values being .β¦ The support of is the set of locations whose value is not β¦, its critical objects are the values and the arguments of the locations in the supportβ¦, and its active objects, with as in (5), are (6)β¦ A control symbol holds in when its value is .β¦
The initial state of on is the state in which every location has value . The run of on is the sequence of states that starts from the initial state, being the result of firing the body in as long as that step is defined.β¦ The roots of the step from are the values of the terms the body evaluates in , along the branch each conditional takes and for every element of the range of each parallel iteration; there are none when holds in .β¦ With as in (6), the objects occurring up to step are (7)β¦ both unions running over the defined states.
For polynomials and with coefficients in , accepts within when for some the state is defined, and hold in it, and the set (7) has at most elements.β¦ A query on inputs is CPT-definable when some CPT program over and polynomials are such that, for every input over a finite set, accepts within exactly when satisfies the query; for this is written .β¦
Interpretation Programs
For a set of binary relation symbols, a finite -structure is a finite set , its universe, with a binary relation on for each .β¦ The formulas of first-order logic with the HΓ€rtig quantifier over are built from , and for by , , and the HΓ€rtig quantifier , which binds in both formulas and is evaluated by (8)
For sets and of binary relation symbols, an interpretation of in consists of a domain formula , a formula identifying pairs, and a formula for each , all in the logic of (8) over ; it sends a finite -structure to the -structure on the pairs that satisfy , identified along , with the relations the define.β¦
An interpretation program over consists of a finite vocabulary of state symbols, an initial interpretation of in , a step interpretation of in , a halting sentence and an output sentence over .β¦ The states of on a finite -structure are and .β¦ The program halts at on when and for every , and accepts when it halts at some with .β¦ The cost of the run up to step is (9)β¦ and is polynomially bounded when there are such that on every finite -structure with universe it halts at some with cost (9) at most .β¦ An interpretation program decides a query when it is polynomially bounded and accepts exactly the structures that satisfy the queryβ¦, and a query is definable by interpretations when some interpretation program decides it.β¦
The Claim
Theorem 1. Let be the separating query.
For all inputs and over finite sets, (10)β¦
For every CPT program over and all polynomials and with coefficients in , there is an input over a finite set with (11)β¦
For every polynomially bounded interpretation program over , there is a finite -structure with (12)β¦
In the paper, the result reads: the query on all finite structures in the fixed vocabulary of eight binary relations is isomorphism-invariant and decidable in deterministic polynomial time, but is not definable in full choiceless polynomial time with counting.
What Is Checked
The library states (10), (11) and (12) over the separating query , given by the system (2), (3) on inputs and on finite -structures, over isomorphisms of inputs, over decision in polynomial time as in (4), over CPT programs accepting within polynomial bounds on their steps and on the objects (7) that occur, and over polynomially bounded interpretation programs in the logic of (8).