November 2000, 27 pp.
Many combinatorial search problems can be expressed as instances of the "constraint satisfaction problem" (CSP). This class of problems is known to be NP-complete in general, so to ensure tractability it is natural to consider restricted subproblems in which the constraints have certain specified forms. The algebraic approach to the CSP maintains that certain algebraic invariance properties of constraints can be used to determine the complexity of these restricted problems.
In 1978 Schaefer classified the complexity of all subproblems of the CSP which arise from restricting the possible constraint types on a two-element domain. This description can be derived by considering the alegbraic structures known as minimal clones on a two-element set, hence, from the point of view of determining complexity, minimal clones are of particular importance.
In the present paper we prove that restricted versions of the CSP in which the constraints are invariant under the term operations of a conservative commutative groupoid are tractable. Using this result, we classify the complexity of all subproblems of the CSP associated with minimal clones on a four-element set.