๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The complexity of constraint satisfaction revisited

โœ Scribed by Alan K. Mackworth; Eugene C. Freuder

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
327 KB
Volume
59
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

โœฆ Synopsis

Mackworth, A.K. and E.C. Freuder, The complexity of constraint satisfaction revisited, Artificial Intelligence 59 (1993) 57-62. This paper is a retrospective account of some of the developments leading up to, and ensuing from, the analysis of the complexity of some polynomial network consistency algorithms for constraint satisfaction problems.

1. Historical context

In 1970 one of us (AKM) worked on an implementation of Huffman-Clowes labeling of line drawings [1 ]. This exploited the consequences of a deceptively simple constraint on the visual world of planar objects: the three-dimensional interpretation of a line as an edge must be the same at both ends. Unfortunately, he observed that standard breadth-first and depthfirst search techniques suffered from severe combinatorial explosions. About the same time the other one of us (ECF) shared a graduate student office in the MIT AI Lab with David Waltz, who was also working on a program to interpret line drawings. Waltz designed a filtering process to remove inconsistent interpretations during the analysis of a scene [21 ], making the

๐Ÿ“œ SIMILAR VOLUMES

On the parallel complexity of discrete r
On the parallel complexity of discrete relaxation in constraint satisfaction networks
โœ Simon Kasif ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 605 KB

## Constraint satisfaction networks have been shown to be a very useful tool for knowledge representation in Artificial Intelligence applications. These networks often utilize local constraint propagation techniques to achieve local consistency (consistent labeling in vision). Such methods have been

Resolution Complexity of Random Constrai
Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
โœ Yong Gao; Joseph Culberson ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 97 KB

Let C 2,k,t n,cn be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions.

Algebra complexity problems involving gr
Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
โœ Steve Seif; Csaba Szabรณ ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 130 KB

In this paper, we connect the constraint satisfaction problem with other complexity problems, like the polynomial equivalence problem for combinatorial 0-simple semigroups, the graph retraction problem and the geometry problem. We show that every constraint satisfaction problem is polynomially equiv