Programming Research Group Research Report RR-02-05

Andrei A. Bulatov

April 2002, 36pp.

Abstract

A wide variety of combinatorial problems can be represented in the form of Constraint Satisfaction Problems (CSP). The general CSP is known to be NP-complete, however some restrictions on the possible form of constraints may lead to a tractable subclass. It has been shown elsewhere that the complexity of subclasses of the constraint satisfaction problem depends only on certain algebraic invariance properties of constraints. In this paper we show that an arbitary 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.