Premium
Property testers for dense constraint satisfaction programs on finite domains
Author(s) -
Andersson Gunnar,
Engebretsen Lars
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10041
Subject(s) - constraint satisfaction problem , property (philosophy) , constraint satisfaction , complexity of constraint satisfaction , arity , probabilistic logic , property testing , constant (computer programming) , constraint (computer aided design) , mathematics , domain (mathematical analysis) , graph , constraint graph , function (biology) , computer science , theoretical computer science , discrete mathematics , local consistency , artificial intelligence , programming language , mathematical analysis , philosophy , geometry , epistemology , evolutionary biology , biology
Many NP‐hard languages can be “decided” in subexponential time if the definition of “decide” is relaxed only slightly. Rubinfeld and Sudan introduced the notion of property testers, probabilistic algorithms that can decide, with high probability, if a function has a certain property or if it is far from any function having this property. Goldreich, Goldwasser, and Ron constructed property testers with constant query complexity for dense instances of a large class of graph problems. Since many graph problems can be viewed as special cases of the Constraint Satisfaction Problem on Boolean domains, it is natural to try to construct property testers for more general cases of the Constraint Satisfaction Problem. In this paper, we give explicit constructions of property testers using a constant number of queries for dense instances of Constraint Satisfaction Problems where the constraints have constant arity and the variables assume values in some domain of finite size. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 14–32, 2002