On Evaluating Boolean Functions with Unreliable Tests
On Evaluating Boolean Functions with Unreliable Tests
复制标题
用不可靠的测试评估布尔函数
DOI：
--
复制
发表时间：
1990
影响因子：
0.8
通讯作者：
A. Yao
中科院分区：
文献类型：
--
作者：
Claire Mathieu;A. Yao
我们考虑的问题，评估一个布尔函数P（x1，...，xn），通过询问形式的查询“xi=？"，得到的答案可能并不总是真实的。假设谎言的总数不超过E，我们给出了一个代价为O（n+sPE+tPE）的算法，其中sP是P（x）中最小项的最大长度，tP '是最大项的最大长度.我们还证明了，如果P是单调的，那么任何算法评估P必须问Ω（sPE+tPE）查询的一些输入。
We consider the problem of evaluating a boolean function P(x1,…,xn), by asking queries of the form “xi=?”, and receiving answers which may not always be truthful. Assuming that the total number of lies does not exceed E, we present an algorithm with cost O(n+sPE+tPE), where sP is the maximal size of a minterm of P(x) and tP ‘is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask Ω(sPE+tPE) queries for some input.