We obtain here the complexity of solving a type of Prolog problem which Geneserth and Nilsson have called sequential constraint satisfaction. 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. An example of this is given, in obtaining a formal basis for the conjunct-ordering heuristic proposed by Warren. Due to the incorporation of ''constraint tightness'' 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. An example of this for Warren's heuristic is also given. [References: 24]
展开▼
