This research is concerned with the development of fast algorithms for constraint satisfaction problem. Constraint satisfaction formations are currently used in many ways, including the generating test of correctness for electronic circuits, the understanding of line drawings by computer, the solution of combinatorial problems, and folding of RNA molecules. The set of constraint satisfaction problems is one of the NP complete problem sets, so it is unlikely that a fast algorithm for all constraint satisfaction problems will ever be found. For several hundred years some of the best researchers have been looking for fast algorithms for NP complete problems sets, and they have never found an algorithm that is fast for every problem in an NP complete set. None the less, algorithms have been found that are fast for most problems in certain NP complete problems sets. This research is concerned with sets where the importance of the problems in the sets vary as parameters associated with the set are varied. By studying the average running time of particular algorithms as the parameters are varied, algorithms that are fast under a wide range of conditions can be found.
