FO (complexity)

In descriptive complexity, a branch of computational complexity, FO is a  complexity class of structures that can be recognized by formulas of first-order logic, and also equals the complexity class AC0. Descriptive complexity uses the formalism of logic, but does not use several key notions associated with logic such as proof theory or axiomatization.

Restricting predicates to be from a set X yields a smaller class FO[X]. For instance, FO[<] is the set of star-free languages.  The two different definitions of FO[<], in terms of logic and in terms of regular expressions, suggests that this class may be mathematically interesting beyond its role in computational complexity, and that methods from both logic and regular expressions may be useful in its study.

Similarly, extensions of first-order logic formed by the addition of operators give rise to other well-known complexity classes. This allows the complexity of some problems to be established without reference to algorithms.

Definition and examples

The idea 
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 " is true iff there is an edge from  to " (in case of the structure being a graph), or " is true iff the 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 almost always suppose 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  represents the number  iff there are  elements  with . Thanks to this we also may have the primitive predicate "bit", where  is true if only the th bit of the binary expansion of  is 1. (We can replace addition and multiplication by ternary relations such that  is true iff  and  is true iff ).

Formally 
Let X be a set of predicates on . The language FO[X] is  defined as the closure by conjunction (), negation () and universal quantification () over elements of the structures. Existential quantification () and disjunction () are also often used but those can be defined by means of the first three symbols. The base case is the predicates of X applied to some variables. One always implicitly has a predicate  for each letter  of an alphabet, stating that the letter at position  is an .

The semantics of the formulae in FO is straightforward,  is true iff  is false,  is true iff  is true and  is true, and  is true iff  is true for all values  that  may take in the underlying universe. For P a c-ary predicate,  is true if and only if when  is interpreted as   is true.

Property

Warning 
A query in FO will then be to check if a first-order formula is true over a given structure representing the input to the problem. One should not confuse this kind of problem with checking if a quantified boolean formula is true, which is the definition of QBF, which is PSPACE-complete. The difference between those two problems is that in QBF the size of the problem is the size of the formula and elements are just boolean variables, whereas in FO the size of the problem is the size of the structure and the formula is fixed.

This is similar to Parameterized complexity but the size of the formula is not a fixed parameter.

Normal form 
Disregarding empty structures, every formula is equivalent to a formula in prenex normal form (where all quantifiers are written first, followed by a quantifier-free formula).

Operators

FO without any operators 

In circuit complexity, FO(ARB) where ARB is the set of all predicates, the logic where we can use arbitrary predicates, can be shown to be equal to AC0, the first class in the AC hierarchy. Indeed, there is a natural translation from FO's symbols to nodes of circuits, with  being  and  of size .

FO(BIT) is the restriction of AC0 family of circuit constructible in alternating logarithmic time. FO(<) is the set of star-free languages.

Partial fixed point is PSPACE 
FO(PFP,X) is the set of boolean queries definable in FO(X) where we add a partial fixed point operator.

Let  be an integer,  be vectors of  variables,  be a second-order variable of arity , and  be a FO(PFP,X) function using  and  as variables. We can iteratively define  such that  and  (meaning  with  substituted for the second-order variable ). Then, either there is a fixed point, or the list of s is cyclic.

 is defined as the value of the fixed point of  on  if there is a fixed point, else as false. Since s are properties of arity , there are at most  values for the s, so with a polynomial-space counter we can check if there is a loop or not.

It has been proven that FO(PFP,BIT) is equal to PSPACE. This definition is equivalent to .

Least Fixed Point is P 
FO(LFP,X) is the set of boolean queries definable in FO(PFP,X) where the partial fixed point is limited to be monotone. That is, if the second order variable is , then  always implies .

We can guarantee monotonicity by restricting the formula  to only contain positive occurrences of  (that is, occurrences preceded by an even number of negations). We can alternatively describe  as  where .

Due to monotonicity, we only add vectors to the truth table of , and since there are only  possible vectors we will always find a fixed point before  iterations. The Immerman-Vardi theorem, shown independently by Immerman and Vardi, shows that FO(LFP,BIT)=P. This definition is equivalent to .

Transitive closure is NL 
FO(TC,X) is the set of boolean queries definable in FO(X) with a transitive closure (TC) operator.

TC is defined this way: let  be a positive integer and  be vector of  variables. Then  is true if there exist  vectors of variables  such that , and for all ,  is true. Here,  is a formula written in FO(TC) and  means that the variables  and  are replaced by  and .

FO(TC,BIT) is equal to NL.

Deterministic transitive closure is L 
FO(DTC,X) is defined as FO(TC,X) where the transitive closure operator is deterministic. This means that when we apply , we know that for all , there exists at most one  such that .

We can suppose that  is syntactic sugar for  where .

It has been shown that FO(DTC,BIT) is equal to L.

Normal form 
Any formula with a fixed point (resp. transitive closure) operator can without loss of generality be written with exactly one application of the operators applied to 0 (resp. )

Iterating 

We will define first-order with iteration, ; here  is a (class of) functions from integers to integers, and for different classes of functions  we will obtain different complexity classes .

In this section we will write   to mean  and  to mean . We first need to define quantifier blocks (QB), a quantifier block is a list  where the s are quantifier-free FO-formulae and s are either  or .
If  is a quantifiers block then we will call  the iteration operator, which is defined as  written  time. One should pay attention that here there are  quantifiers in the list, but only  variables and each of those variable are used  times.

We can now define  to be the FO-formulae with an iteration operator whose exponent is in the class , and we obtain those equalities:
 is equal to FO-uniform ACi, and in fact  is FO-uniform AC of depth .
 is equal to NC.
 is equal to PTIME, it is also another way to write FO(LFP).
 is equal to PSPACE, it is also another way to write FO(PFP).

Logic without arithmetical relations
Let the successor relation, succ, be a binary relation such that  is true if and only if .

Over first order logic, succ is strictly less expressive than <, which is less expressive than +, which is less expressive than bit, while + and × are as expressive as bit.

Using successor to define bit 
It is possible to define the plus and then the bit relations with a deterministic transitive closure.

 and

 with

This just means that when we query for bit 0 we check the parity, and go to (1,0) if  is odd (which is an accepting state), else we reject. If we check a bit , we divide  by 2 and check bit .

Hence it makes no sense to speak of operators with successor alone, without the other predicates.

Logics without successor
FO[LFP] and FO[PFP] are two logics without any predicates, apart from the equality predicates between variables and the letters predicates. They are equal respectively to  relational-P and FO(PFP) is relational-PSPACE, the classes P and PSPACE over relational machines.

The Abiteboul-Vianu Theorem states that FO(LFP)=FO(PFP) if and only if FO(<,LFP)=FO(<,PFP), hence if and only if P=PSPACE. This result has been extended to other fixpoints. This shows that the order problem in first order is more a technical problem than a fundamental one.

References 
 Ronald Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27–41. 1974.
 Ronald Fagin,  Finite model theory-a personal perspective. Theoretical Computer Science 116, 1993, pp. 3–31.
 Neil Immerman. Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp. 347–354. 1983.

External links 
 Neil Immerman's descriptive complexity page, including a diagram
 Complexity zoo about FO, see also the following classes

 
Category:Finite model theory
Category:Complexity classes