Descriptive and Parameterized Complexity

Abstract Descriptive Complexity Theory studies the complexity of problems of the following type: Given a finite structure A and a sentence φ of some logic L, decide if A satisfies φ? 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 (|φ|)‖ A ‖ c, where ƒ 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.

Authors

• Martin Grohe

Keywords

No keywords are indexed for this paper.