3CNF Properties are Hard to Test
Eli Ben‐Sasson, Prahladh Harsha, Sofya Raskhodnikova · 2003
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]. Our results add two novel observations to the recent lower bounds of Bogdanov, Obata and Trevisan [3]. First, notice that deciding P' is easy once all the input is read. Thus, property testing can be hard even for easily computable properties. Second, for every bad instance (i.e. an assignment that does not satisfy ') there is a 3-bit query that proves this fact. Nevertheless, we show that finding such a short witness requires a linear number of queries.