Complexity of Infinite-Domain Constraint Satisfaction

ISBN-13: 9781107042841 / Angielski / Twarda / 2021 / 300 str.

Manuel Bodirsky

Opis

Introduces the universal-algebraic approach to classifying the computational complexity of constraint satisfaction problems.

Recenzje

'… this book is essential reading for anyone with the vaguest interest in computational complexity, as well as for those curious about potential applications of model theory and universal algebra. It brings together decades of intense research by different research communities in a uniform format.' Victor Lagerkvist, MathSciNet

Spis treści

1. Introduction to constraint satisfaction problems; 2. Model theory; 3. Primitive positive interpretations; 4. Countably categorical structures; 5. Examples; 6. Universal algebra; 7. Equality constraint satisfaction problems; 8. Datalog; 9. Topology; 10. Oligomorphic clones; 11. Ramsey theory; 12. Temporal constraint satisfaction problems; 13. Non-dichotomies; 14. Conclusion and outlook; References; Index.