文章基本信息

标题：Mal'tsev constraints are tractable
本地全文：下载
作者：Andrei Bulatov
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of suclasses of the CSP depends only on certain algebraic invariance properties of constraints. The tractability of the problem class raised from a finite group has been proved by Feder and Vardi. In this paper we show that an arbitrary family of constraints invariant with respect to a Mal'tsev operation, that is a ternary operation f(x,y,z) satisfying f(y,y,x)=f(x,y,y)=x for any x,y, gives rise to a tractable problem class. Since every group constraint considered by Feder and Vardi is invariant with respect to a certain Mal'tsev operation, the results of this paper imply the mentioned result of Feder and Vardi.
关键词：complexity , constraint satisfaction problem , Mal'tsev operation