Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-051 | 10th June 2004 00:00

Locally consistent constraint satisfaction problems



An instance of a constraint satisfaction problem is $l$-consistent
if any $l$ constraints of it can be simultaneously satisfied.
For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the general
case of sets $\Pi$ consisting of finitely many Boolean predicates,
we express the limit $\rho_{\infty}(\Pi):=\lim\limits_{l\to\infty}\rho_l(\Pi)$
as the minimum of a certain functional on a convex set of polynomials.
Our technique yields a robust deterministic algorithm (for a fixed
set $\Pi$) running in time linear in the size of the input and
$1/\varepsilon$ which finds either an inconsistent set of constraints
(of size bounded by the function of $\varepsilon$) or a truth
assignment which satisfies the fraction of at least $\rho_{\infty}(\Pi)-\varepsilon$ of the given constraints.
In addition, we compute the values of $\rho_l(\{P\})$ for every predicate $P$ which has arity at most three or which is $1$-extendable.

ISSN 1433-8092 | Imprint