Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-028 | 9th April 1996 00:00

The Optimization Complexity of Constraint Satisfaction Problems


Authors: Sanjeev Khanna, Madhu Sudan
Publication: 10th April 1996 09:49
Downloads: 2886


In 1978, Schaefer considered a subclass of languages in
NP and proved a ``dichotomy theorem'' for this class. The subclass
considered were problems expressible as ``constraint satisfaction
problems'', and the ``dichotomy theorem'' showed that every language in
this class is either in P, or is NP-hard. This result is in sharp
contrast to a result of Ladner, which shows that such a
dichotomy does not hold for NP, unless NP=P.

We consider optimization version of the dichotomy question and show an
analog of Schaefer's result for this case. More specifically, we
consider optimization version of ``constraint satisfaction problems''
and show that every optimization problem in this class is either
solvable exactly in P, or is MAX SNP-hard, and hence not
approximable to within some constant factor in polynomial time,
unless NP=P. This result does not follow directly from Schaefer's result.
In particular, the set of problems that turn out to be hard
in this case, is quite different from the set of languages which are
shown hard by Schaefer's result. A similar result has been
independently shown by Creignou (1995) using different techniques.

ISSN 1433-8092 | Imprint