Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-021 | 10th February 2006 00:00

Constraint satisfaction: a personal perspective


Authors: Tomas Feder
Publication: 14th February 2006 02:59
Downloads: 1603


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.

ISSN 1433-8092 | Imprint