Immerman-Vardi theorem

From Polymath Wiki
Revision as of 05:01, 10 August 2010 by Teorth (talk | contribs) (New page: (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 polyn...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Immerman-Vardi_theorem&oldid=3296"