Descriptive complexity

Logical characterizations of complexity classes on finite structures: Fagin's theorem, Immerman–Vardi (least fixed point and P), and transitive closure logic and NL.

• Fagin's theorem
• Immerman–Vardi theorem
• Transitive closure logic and NL

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.