Is constraint satisfaction over two variables always easy?

By the breakthrough work of Håstad J ACM 48(4) (2001), 798–859], 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 J ACM 42(6) (1995), 1115–1145], we know that every Boolean 2‐CSP has a nontrivial 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²). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, 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 nontrivial 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. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004