The Complexity of Evaluating First-Order Sentences over a Fixed Structure
Andrei Krokhin · 2011
Summary form only given. Both the constraint satisfaction problem and the homomorphism problem are known to be equivalent to the problem of evaluating first-order (∃Λ)-sentences over a relational structure. Many computational problems can be represented in this framework with a suitable fixed relational structure. How exactly does the complexity of the evaluation problem depend on the fixed structure? Much progress has recently been made in answering this question, with an exciting interplay of finite model theory and universal algebra at the heart of this direction. We will explain this interplay and discuss the most important results arising from it. Most of the talk will be devoted to finite structures, but we will touch on the infinite case and also on generalisations to other fragments of first-order logic.