期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：An -test for a property P of functions from = 1 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 d places to make it satisfy P . We prove that an -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 -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.
关键词：comparison model , Monotonicity , Property Testing , random algorithms
-test for a property P of functions from 
