TR96-028 Authors: Sanjeev Khanna, Madhu Sudan

Publication: 10th April 1996 09:49

Downloads: 1645

Keywords:

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.