Immerman-Vardi theorem: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
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... |
(No difference)
|
Revision as of 06:01, 10 August 2010
(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.
