zbMATH — the first resource for mathematics

Descriptive and parameterized complexity. (English) Zbl 0943.03029
Flum, Jörg (ed.) et al., Computer science logic. 13th international workshop, CSL ’99. 8th annual conference of the EACSL, Madrid, Spain, September 20-25, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1683, 14-31 (1999).
Summary: Descriptive complexity theory studies the complexity of problems of the following type: Given a finite structure \(A\) and a sentence \(\varphi\) of some logic \(L\), decide if \(A\) satisfies \(\varphi\).
In this survey we discuss the parameterized complexity of such problems. Basically, this means that we ask under which circumstances we have an algorithm solving the problem in time \(f(|\varphi |)\|A\|^c\), where \(f\) is a computable function and \(c>0\) a constant. We argue that the parameterized perspective is most appropriate for analyzing typical practical problems of the above form, which appear for example in database theory, automated verification, and artificial intelligence.
For the entire collection see [Zbl 0929.00039].

03C13 Model theory of finite structures
68Q19 Descriptive complexity and finite models