This article is cited in 5 papers

The property of being polynomial for Mal'tsev constraint satisfaction problems

A. A. Bulatov

Ural State University

Abstract: A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal'tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time.

UDC: 512.579

Received: 27.01.2006

 English version: Algebra and Logic, 2006, 45:6, 371–388

Bibliographic databases:

• 
• 
•