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 Π of constraint types, ρl(Π) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from Π. In the case of sets Π consisting of finitely many Boolean predicates, we express the limit ρ∞(Π):=liml→∞ρl(Π) as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set Π) running in time linear in the size of the input and 1/ε which finds either an inconsistent set of constraints (of size bounded by the function of ε) or a truth assignment which satisfies the fraction of at least ρ∞(Π)-ε of the given constraints. We also compute the values of ρl({P}) for several specific predicates P.