Constraints Satisfaction Problems (CSPs) belong to the family of NP com-plete problems. The complexity of finding one solution for a CSP is lower or equal to the complexity of finding all the solutions of a CSP, this papers focus on the latter task. Lower upper complexity bounds of solving CSPs were found for CSPs that are represented as graphs of constraints with special properties [1, 3]. This paper presents a new method, for finding upper bounds on the com-plexity of solving CSPs. In many cases this method achieves better bounds than the other methods. An algorithm for finding all solutions of a CSP, and based on this method, is presented. Algorithms previously developed for finding all the solutions of CSPs ([2], [4]) do not manage well loose CSPs. We compare DAP to them, and show that DAP outperforms them in many cases, moreover it is the only algorithm that has a good behavior (both in time and space requirements) for loose CSPs.
展开▼
