Descriptive and parameterized complexity. (English) Zbl 0943.03029

Grohe, Martin

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

MSC:

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

Keywords:

descriptive complexity theory; finite structure; survey; parameterized complexity