Technical Reports

The ICICS/CS Reading Room

UBC CS TR-83-04 Summary

On the Complexity of Achieving K-Consistency, January 1983 Raimund Seidel

A number of combinatorial search problems can be formulated as constraint satisfaction problems. Typically backtrack search is used to solve these problems. To counteract the frequent thrashing behaviour of backtrack search, methods have been proposed to precondition constraint satisfaction problems. These methods remove inconsistencies involving only a small number of variables from the problem. In this note we analyze the time complexity of the most general of these methods, Freuder's $k$-consistency algorithm. We show that it takes worst case time $O(n^{k})$, where $n$ is the number of variables in the problem.

If you have any questions or comments regarding this page please send mail to