The Setting
Does choiceless polynomial time with counting (CPT) capture polynomial time? A CPT program decides a property of a finite structure by computing with sets built from its atoms, and has no order of the atoms to go by; a Turing machine reads the structure written out as a string, which lists the atoms in some order. The two are compared on structures over one vocabulary, where the separating query asks whether a system of linear equations over , read off the structure, has a solution.
The vocabulary is , eight binary relation symbols. An input structure is a finite set of atoms with a binary relation on for each , and a query is a property of input structures.✦ The library defines when a query is definable in CPT, through its own language of terms, rules and runs, and when is decidable in polynomial time, through Turing machines reading an ordered encoding of the structure.
Hereditarily Finite Sets
The set of hereditarily finite sets over a set of atoms is the least set that contains the atoms and every finite subset of itself: (1)✦ An atom has no elements. The transitive closure of is the finite set ✦, and that of a finite family is ✦.
The von Neumann ordinal of is the set of the ordinals below it: (2)✦ The truth value true is . The cardinality operation sends to the ordinal of its number of elements: (3)✦
Terms, Rules and Programs
Fix a finite set of dynamic function symbols, each with an arity, and variables . The CPT terms over and are (4)✦ with , of arity and . Here , and are pairing, union and unique element, is the atom test, and is comprehension with bound , guard and body . The term denotes the set of all atoms, the hereditarily finite set whose members are the elements of taken as atoms.
The CPT rules, built from updates by parallel composition, conditionals, forall and let, are (5)✦
A CPT program over is a finite set of dynamic function symbols with their arities, together with a rule , its body, over and two further symbols and of arity : (6)✦ A state of over is a map that gives every location , a symbol of arity with arguments , a value in , the empty set at all but finitely many locations. The flag or holds in a state when its value there is .✦
Runs and Their Bounds
The run of on an input structure is the sequence of states (7)✦ where is the initial state of on and is the map that executes the body once on a state over ; a step may be undefined, and then so are all later states.
The support of a state is its finite set of locations with a nonempty value✦, and its critical objects are the values and the arguments at those locations✦. The active objects form the transitive closure of the critical objects together with , , and the atoms.✦ The roots of a term at a state are the finitely many objects of that its evaluation at the state constructs from the active objects. The roots of a rule collect those of the terms it evaluates: none for , the arguments and the new value of an update, both parts of a parallel rule, the condition and the branch it selects, the bound and, for each element of its value, the body with , and for a let the bound term and the body with set to its value.✦ The roots of a step from are none when holds in , and otherwise those of at with every variable set to .✦ The objects occurring in the first steps are (8)✦ the unions running over the defined states.
For polynomials with natural coefficients, accepts within time and space when its run reaches, within steps, a state in which both flags hold, with at most objects occurring up to then: (9)✦
The Query and Its Encoding
In an input structure , the configuration atoms are ✦ and the edge atoms ✦; for let . The coefficient of at is (10)✦ and is incident to when and for some and ✦. The structure satisfies the query when there are weights , normalized on every , and , consistent with at every incident pair: (11)✦
An ordered input of size is an input structure on .✦ For an input structure on and a bijection , the ordered copy is the ordered input with (12)✦
List as . The tape code of an ordered input of size is the word over the alphabet that writes in unary, then the letter , then the relation bits: (13)✦
The Definition
Definition 1. A query is definable in CPT if there are a CPT program over and polynomials with natural coefficients such that, for every finite set and every input structure on , in the sense of (9), (14)✦ The query of (11) is decidable in polynomial time if there are a map from ordered inputs to and a multi-tape Turing machine with finite tape alphabets that computes in polynomial time, reading of (13) and writing the one-letter word for true and for false, such that for every finite set , every , every bijection and every input structure on , (15)✦
In the paper, the definitions read: CPT computes on the hereditarily finite sets over the input atoms with set operations, comprehension and the cardinality operation , which returns a von Neumann ordinal, under polynomial bounds on the computation and on the number of recursively occurring objects, and polynomial time means decidability by a deterministic algorithm, polynomial in an ordered encoding, whose answer does not depend on the order.
What Is Checked
Definability in CPT (14) is stated over input structures on finite sets of atoms, CPT programs over with their runs (7) and occurring objects (8), and polynomials with natural coefficients; polynomial time for (15) is stated over the same structures, their ordered copies (12), and multi-tape Turing machines with finite alphabets reading the tape code (13).