|
Published Articles >> Table of Contents >> Abstract
17th Annual IEEE Symposium on Logic in Computer Science (LICS'02)
p. 215
The Complexity of First-Order and Monadic Second-Order Logic Revisited
Markus Frick, University of Edinburgh
Martin Grohe, University of Edinburgh
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2002.1029830
Send link to a friend
| Abstract |
|
The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME = NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f(k) ·p(n),for any elementary function f and any polynomial p. Here k denotes the size of the input sentence and n the size of the input word. We prove the same result for first-order logic under a stronger complexity theoretic assumption from parameterized complexity theory. Furthermore, we prove that the model-checking problems for first-order logic on structures of degree 2 and of bounded degree d\leqslant 3 are not solvable in time 2^(2^{0(k)}} ·p(n) (for degree 2), and 2^{2^{2^{0(k)}}} ·p(n) (for degree d) for any polynomial p, again under an assumption from parameterized complexity theory. We match these lower bounds by corresponding upper bounds.
|
 Additional Information
|
Citation:
Markus Frick, Martin Grohe,
"The Complexity of First-Order and Monadic Second-Order Logic Revisited,"
lics,
p. 215,
17th Annual IEEE Symposium on Logic in Computer Science (LICS'02),
2002
|
|
