__
TR01-008 | 6th November 2000 00:00
__

#### On the strength of comparisons in property testing

**Abstract:**
An $\epsilon$-test for a property $P$ of functions from

${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized

algorithm, which makes queries on the value of an input function at

specified locations, and distinguishes with high probability between the

case of the function satisfying $P$, and the case that it has to be

modified in more than $\epsilon d$ places to make it satisfy $P$.

We prove that an $\epsilon$-test for any property defined in terms of the

order relation, such as the property of being a monotone nondecreasing

sequence, cannot perform less queries (in the worst case) than the best

$\epsilon$-test which uses only comparisons between the queried values. In

particular, we show that an adaptive algorithm for testing that a sequence

is monotone nondecreasing performs no better than the best non-adaptive

one, with respect to query complexity. From this follows a tight lower

bound on tests for this property.