The Setting
Lower bounds for choiceless polynomial time with counting (CPT) are proved through the counting logic , first-order logic with equality, existential and exact counting quantifiers and variable names: a computation whose answer is given by a sentence of answers alike on any two structures that does not distinguish. Encoding the complete run of a choiceless computation in this way substitutes the formulas of the program into one another, and the number of names the result needs has to stay bounded.
This item bounds that number for interpretation programs, whose formulas are in first-order logic with the Härtig quantifier (FO+H), and it counts names through the relations that a fixed palette of names can define, wherever their arguments are placed on it.
Counting Logic and Definability
A binary relational structure over a vocabulary is a set , its universe, with a binary relation on for each symbol .✦ The formulas of over are built from , the equations and the atoms with and , by negation, conjunction, the existential quantifier and, for each , the counting quantifier .✦ The free variables of a formula of are the names that occur in it outside the scope of a quantifier binding them.✦ Satisfaction of a formula of under an assignment of elements of to the names is defined as usual, with true when exactly elements satisfy under changed to send to .✦
An -ary relation on the universe of is definable with names if for every map , injective or not, there is a formula of over , with free variables among , such that (1)✦ A family of -ary relations, each on the universe of a binary relational structure over , is uniformly definable with names if for every map there is one formula of , with free variables among , that satisfies (1) in every with in place of .✦
Härtig Logic, Width and Programs
A finite structure over a set of binary relation symbols is a finite set , its universe, with a binary relation on it for each .✦ The formulas of FO+H over in variables are generated from , the equations and the atoms with by negation and conjunction, and by and the Härtig quantification for formulas and in the variables .✦ Satisfaction of a formula of FO+H in variables at a tuple is defined as usual, with true at when as many elements satisfy as satisfy .✦
The scoped width of a formula of FO+H is the largest number of variables in scope at an atomic subformula of , with counted as atomic: (2)✦
Let and be sets of binary relation symbols. A two-dimensional interpretation of structures over in structures over is a family of formulas of FO+H over : a domain formula in two variables and, with and pairs of variables, an equivalence formula in four variables and, for each , a relation formula in four variables.✦ An interpretation program over a set of binary relation symbols consists of a finite set of binary relation symbols, the state symbols, an interpretation of structures over in structures over , an interpretation of structures over in structures over , and two sentences of FO+H over , the halting condition and the output condition .✦
The Claim
Theorem 1. Let be a family of binary relational structures over with universes .
Let be natural numbers, and suppose the family of -ary relations on is uniformly definable with names. Then so is the family of -ary relations (3)✦ and so, for each , is the family (4)✦
Let be natural numbers, and suppose the families of -ary relations and on are uniformly definable with names. Then for each bound so is the family of tuples at which the two counts agree and are at most , the bounded Härtig comparison, (5)✦
Let and be natural numbers, let , for , be finite structures over with maps , and let be a formula of FO+H over in variables with . Then there is a family of -ary relations on , uniformly definable with names, such that for every and all (6)✦
For every interpretation program , with state symbols , there is a natural number such that (7)✦
In the paper, the result reads: substituting formulas of free-variable measure at most into a relational formula , without capture, gives a formula of measure at most , and a formula of measure at most can be renamed to use at most variable names.
The box states this in semantic form, with definability with names in place of a count of the names a formula uses.
What Is Checked
The claims are stated over binary relational structures and the counting logic on them, with its free variables, its satisfaction and definability with names in plain and uniform form, and over finite structures, the logic FO+H with its satisfaction, scoped width, two-dimensional interpretations and interpretation programs.