ECCC-Report TR02-053https://eccc.weizmann.ac.il/report/2002/053Comments and Revisions published for TR02-053en-usWed, 18 Sep 2002 09:48:08 +0300
Paper TR02-053
| Is Constraint Satisfaction Over Two Variables Always Easy? |
Lars Engebretsen,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2002/053By the breakthrough work of HÃ¥stad, several constraint satisfaction
problems are now known to have the following approximation resistance
property: satisfying more clauses than what picking a random
assignment would achieve is NP-hard. This is the case for example for
Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable exception
to this extreme hardness is constraint satisfaction over two variables
(2-CSP); as a corollary of the celebrated Goemans-Williamson
algorithm, we know that every Boolean 2-CSP has a non-trivial
approximation algorithm whose performance ratio is better than that
obtained by picking a random assignment to the variables. An
intriguing question then is whether this is also the case for 2-CSPs
over larger, non-Boolean domains. This question is still open, and is
equivalent to whether the generalization of Max 2-SAT to domains of
size d, can be approximated to a factor better than (1 - 1/d^2).
In an attempt to make progress towards this question, in this paper we
prove, firstly, that a slight restriction of this problem, namely a
generalization of linear inequations with two variables per
constraint, is not approximation resistant, and, secondly, that the
Not-All-Equal Sat problem over domain size d with three variables per
constraint, is approximation resistant, for every d >= 3. In the
Boolean case, Not-All-Equal Sat with three variables per constraint is
equivalent to Max 2-SAT and thus has a non-trivial approximation
algorithm; for larger domain sizes, Max 2-SAT can be reduced to
Not-All-Equal Sat with three variables per constraint. Our
approximation algorithm implies that a wide class of 2-CSPs called
regular 2-CSPs can all be approximated beyond their random assignment
threshold.
Wed, 18 Sep 2002 09:48:08 +0300https://eccc.weizmann.ac.il/report/2002/053