The Complexity of Constraint Satisfaction in Prolog

Bernard A. Nadel

We obtain here the complexity of solving a type of Prolog problem which Genesereth and Nilsson have called sequential constraint satisfactrlon. Such problems are of direct relevance to relational database retrieval as well as providing a tractable first step in analyzing Prolog problem-solving in the general case. The present paper provides the first analytic expressions for the expected complexity of solving sequential constraint satisfaction problems. These expressions provide a basis for the formal derivation of heuristics for such problems, analogous to the theory-based heuristics obtained by the author for traditional constraint satisfaction problem-solving. A first application has been in providing a formal basis for Warren’s heuristic for optimally ordering the goals in a conjunctive query. Due to the incorporation of "constraint looseness" into the analysis, the expected complexity obtained here has the useful property that it is usually quite accurate even for individual problem instances, rather than only for the assumed underlying problem class as a whole. Heuristics based on these results can be expected to be equally instance-specific. Preliminary results for Warren’s heuristic have shown this to be the case.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.