The Setting
The separating query is the query used to show that choiceless polynomial time with counting does not capture polynomial time. It is a property of finite structures over a vocabulary of eight binary relations. Two kinds of element, edge atoms and configuration atoms, index the unknowns of a system of linear equations over the three-element field whose coefficients are read off the relations, and holds when that system has a solution.
The vocabulary is the set of eight binary relation symbols (1)✦ with one symbol for each .
An input structure on a set is a -structure with universe : it interprets each symbol as a binary relation on , (2)✦ With fixed, means .
An isomorphism from an input structure on to an input structure on is a bijection that preserves every relation of in both directions: (3)✦
The edge atoms of an input structure on are the elements that relates to themselves, and its configuration atoms are those that relates to themselves: (4)✦ (5)✦ For a configuration atom we write .
For an input structure on a finite set , the coefficient of an edge atom at a configuration atom is the element of (6)✦
A configuration atom is incident to an edge atom if (7)✦
A weighting of the configuration atoms is normalized if (8)✦ A pair of weightings and is consistent if (9)✦
The Definition
Definition 1. Let be an input structure on a finite set, with configuration atoms and edge atoms . The separating query is the property of given by (10)✦
What Is Checked
The definition (10) is stated over input structures (2) on a finite set for the vocabulary of (1), through their edge atoms (4), configuration atoms (5), coefficients (6) and incidence (7), and over the conditions (8) and (9) on weightings with values in .