Immerman-Vardi theorem
From Polymath Wiki
(More discussion needed!)
- Theorem (Immerman-Vardi). Over finite, ordered structures, the queries expressible in the logic FO(LFP) are precisely those that can be computed in polynomial time. Namely, FO(LFP) = P.
- [I1986] N. Immerman, "Relational queries computable in polynomial time", Information and Control 68 (1986), 86-104
- [V1982] M. Vardi, Complexity of Relational Query Languages, 14th Symposium on Theory of Computation (1982), 137-146.
