The Setting
Choiceless polynomial time with counting computes on a finite structure without ever choosing an element, so all it can build is what is definable from the input as a whole. Interpretation programs give such a computation a form with no machine in it: a run is a sequence of finite structures, each defined from the one before by a logical interpretation in first-order logic with the Härtig quantifier.
Structures and Formulas
Fix a set of binary relation symbols. A finite structure over is a finite set , its universe, together with a binary relation on for each : (1)✦
The formulas of first-order logic with the Härtig quantifier, , over in the variables are generated by (2)✦ with and ; in the last two clauses and are formulas in the variables , and is bound.
Satisfaction of a formula in variables under an assignment is the usual one for , equality, atoms, , and , and for the Härtig quantifier it is (3)✦ with assigned to . A sentence over is a formula of over in no variables; it holds in , written , when it is satisfied under the empty assignment.✦
Interpretations
Let and be sets of binary relation symbols. A two-dimensional interpretation of structures over in structures over is a family of formulas of over , (4)✦ made of a domain formula in two variables, an equivalence formula in four, and a relation formula in four for each symbol .
Let be a finite structure over . The domain of on is the set of pairs (5)✦ Two pairs are linked when ✦, and is the equivalence relation on generated by the links, the smallest one containing them.✦ The interpreted structure is the finite structure over whose universe is the set of classes , and in which holds between two classes when some representatives of them satisfy : (6)✦
The Definition
Definition 1. Let be a set of binary relation symbols. An interpretation program over is a tuple (7)✦ where is a finite set of binary relation symbols, the state symbols, is an interpretation of structures over in structures over , is an interpretation of structures over in structures over , and the halting condition and the output condition are sentences of over .
Let be a finite structure over . The state of after steps on is the finite structure over given by (8)✦ A natural number is the first halting step of on when (9)✦ The cost of on up to step is the number of the states plus the sum of their sizes, (10)✦ The program accepts when it has a first halting step on and (11)✦ The program over is polynomially bounded when there are natural numbers and such that on every finite structure over the program has a first halting step with (12)✦ For a query , a property of finite structures over , the program decides when it is polynomially bounded and, for every finite structure over , (13)✦
In the paper, the result reads: an interpretation is given by formulas , and of first-order logic with the Härtig quantifier, its universe is the domain modulo the equivalence generated by , and holds on classes when some representatives satisfy , while a program with init and step interpretations and sentences and halts at the first stage with , and is polynomially bounded, the paper writing for .
What Is Checked
The definition is stated over finite structures over sets of binary relation symbols, the formulas of first-order logic with the Härtig quantifier with their satisfaction relation, and two-dimensional interpretations, applied to a structure by taking the pairs that satisfy modulo the equivalence generated by .