Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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....

share|improve this question
I recommend this link. –  Yuval Filmus May 9 '12 at 4:38

1 Answer 1

up vote 1 down vote accepted

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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.