1
$\begingroup$

In descriptive complexity theory, FO is the set of properties (problem) expressible by first-order logic.

I get this part, but what are all these transitive operators and some structures?

From Wikipedia:

First-order logic defines the class FO, corresponding to $AC_{0}$, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time. First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space. First-order logic with a transitive closure operator yields NL, the problems solvable in nondeterministic logarithmic space. In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. Existential second-order logic yields NP, as mentioned above.

What is the difference between all aforementioned things and predicate/function?

I am not getting this well....

  • 1
    I recommend [this link](http://www.google.ca/search?rls=en&q=descriptive+complexity+theory+lecture+notes).2012-05-09

1 Answers 1

1

Operators like Transitive Closure (TC) are new ways of building formulas from other formulas, similar to logical connectives (AND, OR, etc.) and quantifiers. They are not new function/relation symbols in the non-logical part of the language. The second difference is that their meaning is fixed a priory. It might also help to think of them as a new kind of quantifiers (though this is not completely correct in general, quantifiers are a very special kind of operators).