ECCC-Report TR02-034https://eccc.weizmann.ac.il/report/2002/034Comments and Revisions published for TR02-034en-usTue, 18 Jun 2002 16:43:47 +0300
Paper TR02-034
| Mal'tsev constraints are tractable |
Andrei Bulatov
https://eccc.weizmann.ac.il/report/2002/034A 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.
Tue, 18 Jun 2002 16:43:47 +0300https://eccc.weizmann.ac.il/report/2002/034