Abstract

For a boolean formula φ on n variables, the associated property Pφ is the collection of n-bit strings that satisfy φ. We prove that there are 3CNF properties that require a linear number of queries, even for adaptive tests. This contrasts with 2CNF properties that are testable with O(√n) queries[7]. Notice that for every bad instance (i.e. an assignment that does not satisfy φ) there is a 3-bit query that witnesses this fact. Nevertheless, finding such a short witness requires a linear number of queries, even for assignments that are very far from satisfying.We provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include a couple of observations which are of independent interest.

Keywords

Computer scienceProperty (philosophy)NoticeTheoretical computer scienceBoolean functionProperty testingTest (biology)Discrete mathematicsAlgorithmMathematicsCombinatorics

Affiliated Institutions

Related Publications

Publication Info

Year
2003
Type
article
Pages
345-354
Citations
26
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

26
OpenAlex

Cite This

Eli Ben‐Sasson, Prahladh Harsha, Sofya Raskhodnikova (2003). Some 3CNF properties are hard to test. , 345-354. https://doi.org/10.1145/780542.780594

Identifiers

DOI
10.1145/780542.780594