Mackworth and Freuder also proved that backtracking can be applied to CSPs   The backtracking algorithm is usually implemented by a linear non deterministic technique being therefore a polynomial algorithm on non deterministic machines The backtracking technique is applicable to MC   as well  so we can perform a poly nomial solution of MSAT on nondeterministic machines  This shows that MSAT is in NP
and allows us to claim

## Theorem 2 Msat Mc Is Np-Complete.

Because of this negative result a deep investigation is needed to define tractable sub classes of the set of    relations which allow us to perform polynomial analysis for at least a subset of the networks of constraints definable on MC
In this paper we give the definition of the three maximal tractable subclasses of MC
exhibiting therefore a complete classification of tractability for the algebra  The three maximal tractable subclasses have already been studied by Anger  Mitra and Rodriguez in They obtain maximality of the algebras  and exhibited O n 3   algorithms   We have three main differences here with respect to their paper The number of classes we individuated is lower than theirs  because they found four maximal tractable subclasses They failed to note that one of the four subalgebras is a subset of another one In Table the subalgebra Mss corresponds to the fourth algebra of Anger  Mitra and Rodriguez   This subalgebra is tractable  but not maximal The algorithms we exhibit are all O n 2 while Anger Mitra and Rodriguez exhibited only an O n 3 algorithm for one of the three maximal subsets Our classification is complete Thus any subset of MC which is not a subset of one of the three maximal tractable subalgebras we individuated is intractable   Anger  Mitra and Rodriguez did not find this result  since they did not analyse all the subalgebras of PO time algebra  as we did for MC

## 4. Maximal Tractable Subclasses Of Mc-4

Given a subset S of a constraint algebra A  we indicate by S the set formed by all the relations of A which can be written as expressions of the algebra involving only elements of S and the operations of composition intersection and converse of relations This set is often called the transitive closure of S with respect to the operations above  We refer to it as the closure of S A set S which coincides with its closure is called a subalgebra In the previous section we recall the result on NP completeness for MC
The first important observation on the complexity of subalgebras is that  when a subalgebra B does not contain the empty relation then a network of constraints on B cannot entail a strict contradiction then it is consistent So far the problem is necessarily polynomially solvable This is stated in the next lemma because it is O
Lemma 2 Given an algebra A, if a subalgebra B of A does not contain the empty relation, then SAT B  is polynomial.