The Setting
Choiceless polynomial time with counting (CPT) does not capture polynomial time: there is a query on finite structures that a polynomial-time algorithm decides and no CPT program defines. Proposition 2 is the upper bound.
A structure for describes a system of linear equations over the field of integers modulo , with unknowns attached to elements of the structure, and asks whether the system has a solution. Gaussian elimination decides it.
The Query
The vocabulary consists of eight binary relation symbols: , , , , , and for each .✦ An input structure on a set is a -structure with universe : it interprets each as a binary relation on .✦ An isomorphism from an input structure on to an input structure on is a bijection such that holds exactly when does, for every and all .✦
The edge atoms of an input structure on a finite set form the set ✦, its configuration atoms the set ✦, and for we write , the relations being those of . The coefficient of an edge atom in a configuration atom is the element of (1)✦ A configuration atom is incident to an edge atom if there are and with and .✦
A weighting of is a pair of maps and . The map is normalized if (2)✦ and a weighting of is consistent if (3) The query holds of if has a consistent weighting with normalized.
Linear Systems and Elimination
A linear equation over in unknowns consists of coefficients and a right-hand side ✦, and a vector satisfies it if .✦ A linear system in unknowns is a finite sequence of such equations, and it is solvable if one vector satisfies all of them.✦
Gaussian elimination computes a verdict one unknown at a time. With no unknowns left, the verdict is if every right-hand side is , and otherwise. With unknowns, if some equation has a nonzero coefficient at the first unknown, it serves as pivot, and a multiple of it is subtracted from each equation to make that coefficient ; pivot or not, the first unknown is then dropped. Counted elimination performs the same elimination and also returns an operation count : for a system of equations it charges for each unknown dropped while remain, and for the final check.✦
An ordered input of size is an input structure on .✦ The linear system of an ordered input of size has the unknowns and equations. First comes, for each , the equation of (2) when ; then, for each pair in lexicographic order, the equation of (3) when , and is incident to ; every other equation is .✦ The decision is the verdict of counted elimination on .✦ The answer is the verdict of Gaussian elimination on with each equation written as the list of its coefficients and its right-hand side.✦
The Machine
The ordered encoding of an ordered input of size is the word (4)✦ over the alphabet consisting of the blank symbol and the digits , where the table lists the truth values of , with for true, for in the order , , , , , , , and in lexicographic order.
The machine that decides on ordered encodings is a multi-tape Turing machine in which each tape is a stack, built from programs in three languages: stack programs, counter programs and bounded programs. A stack program acts on finitely many stacks and a control value from a finite set. Its atomic actions push a letter computed from the control, read or pop the top letter of a stack into the control, update the control, and branch on it✦; programs are built from them by sequencing, conditionals and while loops on a test of the control.✦ A run between two stores, each a control value with the contents of every stack, takes one step for an atomic action and for leaving a loop, and one step more than its parts for a sequence, a conditional or a pass through a loop.✦ Some stack programs are fixed once and for all: they move, copy and clear stacks, and combine the contents of two stacks, each read as a row of letters, letter by letter. Each stack program compiles into a multi-tape Turing machine whose tapes are its stacks, one of them for input and one for output, and whose states are the nodes of the program, namely its atomic actions and the programs built from them; the start and the exit of the program are the nodes at which a run of it begins and ends.✦
A counter program has finitely many registers holding natural numbers, a finite control, an input word and an output word. Its atomic actions update the control, set a register to zero, increment or decrement it, test whether it is positive, copy or add one register into another, look up an input letter by a register, consume the next input letter and emit an output letter; they combine as in stack programs.✦ A counter program compiles into a stack program that keeps each register in unary on a stack of its own, beside stacks for the input and the output and three scratch stacks.✦
The letters of the counter programs, of the elimination program and of the query program are the scalars of together with a blank , which also separates rows.
A bounded program has five index variables and a finite control. It is built by sequencing from updates of the control, emissions of a letter, reads of the table bit for and index variables , tests of , and loops in which an index variable runs through .✦ The time bound of a bounded program , with , charges for an update, for an emission, for a read, for a test, one more than the sum of the parts for a sequence, and for a loop with body .✦ A bounded program compiles into a counter program with registers for , for , for each index variable and its remaining count, and for scratch values.✦
The matrix program is the bounded program that emits , each equation as its coefficients, its right-hand side and a blank , with incidence and each coefficient computed by loops over the universe.✦ The elimination program is a stack program that keeps the equations on a matrix stack and performs the Gaussian elimination described above on the columns, writing the verdict to its output.✦
The query program reads off the leading blanks of its input, runs the compiled matrix program, moves the emitted equations and in unary onto the stacks of the elimination program, runs it, and clears what remains of the input.✦ The query machine is the Turing machine compiled from the query program✦, and its step bound is (5)✦
The Claim
Theorem 1. Let and be input structures on finite sets, and suppose there is an isomorphism from to . Then (6)✦ For every linear system over , (7)✦ For every ordered input of size , (8)✦ (9)✦ (10)✦ (11)✦ There is a polynomial with natural-number coefficients such that, for every , (12)✦ There are a multi-tape Turing machine and a polynomial such that, for every ordered input of size , the machine started with on its input tape halts within steps with a one-letter output , and (13)✦
What Is Checked
The claim is stated over input structures, their isomorphisms and the query in (6); over linear systems over and Gaussian elimination in (7); over ordered inputs, their systems , counted elimination and the answer in (8), (9), (10) and (11); over the step bound of the query machine in (12); and over multi-tape Turing machines and the ordered encoding (4) in (13).
About the programs, the library proves that a run of a stack program from one store to another in steps is followed by every Turing machine containing the program’s compiled code, which passes within steps from the first store at the program’s start to the second at its exit✦, and for the compiled machine itself the exit is halting. It also proves that the query program, started with on its input stack and every other stack empty, runs in at most steps to the store in which every stack is empty except the output stack, which holds the one letter .✦