In Figure an algorithm is presented which solves the problem of consistency checking for the subalgebra M 81 We can show  in particular  the following claim Theorem 7 Algorithm M81-CONSISTENCY correctly decides the consistency of a network of constraints T on M 81 in O n 2 steps where n is the number of vertices of T .

## Proof

By Lemma   we can ensure the correctness of Algorithm M    CONSISTENC    The com plexity of the algorithm can be derived from the fact that the computation of strongly connected components is a O e  problem where e is the number of edges in the network The ¥81 implementation adds in the worst case O e' edges where e' is the number of edges in T  and therefore the number of edges in Ψ s 1 T  is O    e ′   which is clearly O n 2
□
An immediate consequence of Theorem is the following Theorem 8 MSAT M81  is polynomial.

The subalgebras included in M 81 are in Table of Appendix A

## 5. Conclusions

We presented a classification of tractability which is complete for the spatial algebra MC
This classification states that there exist three maximal tractable subalgebras M 72 M 99 and M 81 which include    out of      expressive subalgebras of MC
The interest in a complete classifications of tractability as already observed by Jonsson is determined by the need for a definition of the boundary between and Drakengren tractable and intractable problems  Nebl         has suggested that the knowledge of this boundary can be used either as preprocessing step and as a way to structure the backtracking search on such algebras The provision of a complete classification is one step in researching about constraint algebras A next step is the individuation of useful heuristics which give improvements in the performances of various techniques  We are currently exploiting the use of these techniques in association with techniques based on the classification presented in this paper to obtain efficient reasoning algorithms which can be used in practice Preliminary results on path consistency are encouraging but we cannot yet guarantee the percentage of improvement since the algebra MC is so simply structured that for networks randomly chosen it is very hard to obtain a case where inconsistency is not detectable by path consistency

## Acknowledgements

I would like to thank Elena Mutinelli who developed her Laurea Thesis  Mutinelli on the theme of complexity of reasoning about congruence and first discussed preliminary