__
TR06-021 | 10th February 2006 00:00
__

#### Constraint satisfaction: a personal perspective

**Abstract:**
Attempts at classifying computational problems as polynomial time

solvable, NP-complete, or belonging to a higher level in the polynomial

hierarchy, face the difficulty of undecidability. These classes, including

NP, admit a logic formulation. By suitably restricting the formulation, one

finds the logic class MMSNP, or monotone monadic strict NP without

inequality, as a largest class that seems to avoid diagonalization

arguments. Representative of this logic class is the class CSP of

constraint satisfaction problems. Both MMSNP and CSP admit generalizations

via alternations of quantifiers corresponding to higher levels in the

hierarchy. Examining CSP from a computational point of view, one finds

that the polynomial time solvable problems that do not have the bounded

width property of Datalog are group theoretic in nature. In general,

closure properties of the constraints characterize the complexity of

the problems. When one restricts the number of occurrences of each

variable, the problems that are encountered relate to delta-matroid

intersection. When such a restriction forbidding copying is introduced

in the context of input-output constraints, one finds nonexpansive

mappings as characterizing this restriction. Both delta-matroid

intersection and nonexpansive network stability problems yield polynomial

time algorithms. When the general approach to the classification of

constraint satisfaction problems is restricted to graphs and digraphs,

one finds that the chordality of graphs plays a crucial role both for

the structure of allowed constraints and for the structure of an instance.