Report Number: CS-TN-96-29
Institution: Stanford University, Department of Computer Science
Title: The Optimization Complexity of Constraint Satisfaction
Author: Khanna, Sanjeev
Author: Sudan, Madhu
Date: December 1995
Abstract: 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.