




















An $ε$-test for any non-trivial property (one for which there are both satisfying inputs and inputs of large distance from the property) should use a number of queries that is at least inversely proportional in $ε$. However, to the best of our knowledge there is no reference proof for this intuition. Such a proof is provided here. It is written so as to not require any prior knowledge of the related literature, and in particular does not use Yao's method.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。