Editing Descriptive complexity theory (section)

==The setting==

When we use the logic formalism to describe a computational problem, the input is a finite structure, and the elements of that structure are the [[domain of discourse]]. Usually the input is either a string (of bits or over an alphabet) and the elements of the logical structure represent positions of the string, or the input is a graph and the elements of the logical structure represent its vertices. The length of the input will be measured by the size of the respective structure.
Whatever the structure is, we can assume that there are relations that can be tested, for example "<math>E(x,y)</math> is true if and only if there is an edge from {{mvar|x}} to {{mvar|y}}" (in case of the structure being a graph), or "<math>P(n)</math> is true if and only if the {{mvar|n}}th letter of the string is 1." These relations are the predicates for the first-order logic system. We also have constants, which are special elements of the respective structure, for example if we want to check reachability in a graph, we will have to choose two constants ''s'' (start) and ''t'' (terminal).

In descriptive complexity theory we often assume that there is a total order over the elements and that we can check equality between elements. This lets us consider elements as numbers: the element {{mvar|x}} represents the number {{mvar|n}} if and only if there are <math>(n-1)</math> elements {{mvar|y}} with <math>y<x</math>. Thanks to this we also may have the primitive predicate "bit", where <math>bit(x,k)</math> is true if only the {{mvar|k}}th bit of the binary expansion of {{mvar|x}} is 1. (We can replace addition and multiplication by ternary relations such that <math>plus(x,y,z)</math> is true if and only if <math>x+y=z</math> and <math>times(x,y,z)</math> is true if and only if <math>x*y=z</math>).