ECCC-Report TR06-021https://eccc.weizmann.ac.il/report/2006/021Comments and Revisions published for TR06-021en-usTue, 14 Feb 2006 02:59:46 +0200
Paper TR06-021
| Constraint satisfaction: a personal perspective |
Tomas Feder
https://eccc.weizmann.ac.il/report/2006/021Attempts 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.
Tue, 14 Feb 2006 02:59:46 +0200https://eccc.weizmann.ac.il/report/2006/021