Structure and Specification as Sources of Complexity

Anuj Dawar
If computational complexity is the study of what makes certain computational problems inherently difficult to solve, an important contribution of descriptive complexity in this regard is the separation it provides between the specification of a decision problem and the structure against which this specification is checked. The formalisation of these two aspects leads to tools for studying them as sources of complexity, and on the one hand leads to results in the characterisation of complexity...