Capturing complexity classes by fragments of second order logic
Erich Grädel · 2002
The expressive power of certain fragments of second-order logic on finite structures is investigated. The fragments are second-order Horn logic, second-order Krom logic, and a symmetric and a deterministic version of the latter. It is shown that all these logics collapse to their existential fragments. In the presence of a successor relation they provide characterizations of polynomial time, deterministic and nondeterministic logspace and of the complement of symmetric logspace. Without a successor relation these logics can still express certain problems that are complete in the corresponding complexity classes, but they are strictly weaker than previously known logics for these classes and fail to express some very simple properties.>