Testing Assignments to Constraint Satisfaction Problems
Journal Articles
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
For a finite relational structure A, let CSP(A) denote the CSP instances
whose constraint relations are taken from A. The resulting family of problems
CSP(A) has been considered heavily in a variety of computational contexts. In
this article, we consider this family from the perspective of property testing:
given an instance of a CSP and query access to an assignment, one wants to
decide whether the assignment satisfies the instance, or is far from so doing.
While previous works on this scenario studied concrete templates or restricted
classes of structures, this article presents comprehensive classification
theorems.
Our first contribution is a dichotomy theorem completely characterizing the
structures A such that CSP(A) is constant-query testable: (i) If A has a
majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query
testable with one-sided error. (ii) Else, testing CSP(A) requires a
super-constant number of queries. Let $\exists$CSP(A) denote the extension of
CSP(A) to instances which may include existentially quantified variables.
Our second contribution is to classify all structures A in terms of the
number of queries needed to test assignments to instances of $\exists$CSP(A),
with one-sided error. More specifically, we show the following trichotomy: (i)
If A has a majority polymorphism and a Maltsev polymorphism, then
$\exists$CSP(A) is constant-query testable with one-sided error. (ii) Else, if
A has a $(k + 1)$-ary near-unanimity polymorphism for some $k \geq 2$, and no
Maltsev polymorphism then $\exists$CSP(A) is not constant-query testable (even
with two-sided error) but is sublinear-query testable with one-sided error.
(iii) Else, testing $\exists$CSP(A) with one-sided error requires a linear
number of queries.
