The Setting
A program of choiceless polynomial time computes over a finite structure by building hereditarily finite sets over its atoms. Forms describe such sets from a short tuple of atoms, a molecule, through the counting types of tuples alone: a form is a finite labelled tree, and its value at a molecule is a hereditarily finite set over the atoms. With molecules of length one, a form can send an atom to the set of atoms for which the pair has a prescribed type , and deeper forms give sets of such sets.
Counting Types and Hereditarily Finite Sets
A binary relational structure over a vocabulary with universe interprets every symbol as a binary relation on ; the elements of are its atoms.✦
A formula of the counting logic over with variable names from a set is falsity, an equation or a relational atom between names, or is built from formulas by negation, conjunction, existential quantification and exact counting quantification: (1)✦ with , and , where says that exactly values of satisfy . The counting logic over consists of the formulas (1) whose variable names come from a set of names.
Fix a finite set of positions. A molecule of is a tuple of atoms, one at each position; for it is a tuple of atoms. Fix also an injective map , naming two copies of the positions. The type of two molecules and is the set of formulas (1) that hold in when each name denotes and each name denotes .
The set of hereditarily finite sets over the atoms is the least set that contains every atom of and every finite set of its own elements.✦
The Definition
Definition 1. Let be a set of positions, not necessarily finite, and a set of labels. The set of forms over with labels in is the least set that contains an atomic form for each position and, for every , forms and labels , the set form listing the pairs : (2)✦ Now let be finite, let be a finite binary relational structure over with universe , let be as above, and let the labels be sets of counting formulas over and . The value of a form at a molecule is defined by recursion on : (3)✦
In the paper, the result reads: a molecule is a tuple of atoms, the forms are the atomic forms and the set forms, finite sets of pairs with a form and a realized type of length , and and , where is the universe , , is the logic with , and is the type in .
What Is Checked
The forms (2) are defined over any set of positions and any set of labels, and their value (3) over a finite binary relational structure with universe , a finite set of positions, an injective naming of two copies of by variable names of the counting logic, and labels that are sets of counting formulas.