For a boolean formula \phi on n variables, the associated property
P_\phi is the collection of n-bit strings that satisfy \phi. 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(\sqrt{n}) queries [FLNRRS2002]. Our
results add two novel observations to the recent lower bounds of
Bogdanov, Obata and Trevisan. First, notice that deciding P_\phi 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 \phi) 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.

We provide a general characterization of linear properties that are hard
to test, and in the course of the proof include a couple of
observations which are of independent interest.

1. In the context of linear property testing, adaptive 2-sided error
tests have no more power than non-adaptive 1-sided error tests.

2.Random linear codes with linear distance and constant rate are
very far from being locally testable.