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... |
Setting up another stub |
||
| Line 1: | Line 1: | ||
(More discussion needed!) | (More discussion needed!) | ||
: '''Theorem (Immerman-Vardi)'''. Over finite, ordered structures, the queries expressible | : '''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. | ||
in the logic FO(LFP) are precisely those that can be computed in polynomial time. Namely, FO(LFP) = P. | |||
* [I1986] N. Immerman, "[http://www.cs.umass.edu/~immerman/pub/query.pdf 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. | |||
Revision as of 05: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.
- [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.
