文章基本信息

标题：The Complexity of Constraint Satisfaction Problems (Invited Talk)
本地全文：下载
作者：Manuel Bodirsky
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：30
页码：2-9
DOI：10.4230/LIPIcs.STACS.2015.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The tractability conjecture for constraint satisfaction problems (CSPs) describes the constraint languages over a finite domain whose CSP can be solved in polynomial-time. The precise formulation of the conjecture uses basic notions from universal algebra. In this talk, we give a short introduction to the universal-algebraic approach to the study of the complexity of CSPs. Finally, we discuss attempts to generalise the tractability conjecture to large classes of constraint languages over infinite domains, in particular for constraint languages that arise in qualitative temporal and spatial reasoning.
关键词：constraint satisfaction; universal algebra; model theory; clones; temporal and spatial reasoning