ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS

作     者：CLAIRE KENYON ANDREW C. YAO 

作者机构：DIMACS Center Rutgers University Piscataway NJ 08855 USA Ecole Normale Supérieure 45 rue d’Ulm 75230 Paris Cedex 05 France Research supported by the graduate exchange program between Ecole Normale Supérieure and Princeton University. Computer Science Dept Princeton University Princeton NJ 08544 USA Research supported in part by NSF under grants DCR83–08109 and CCR-8813283. 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1990年第1卷第1期

页      面：1-10页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：algorithms boolean functions error correction lower bounds unreliable tests 

摘      要：We consider the problem of evaluating a boolean function P(x 1 ,…,x n ), by asking queries of the form “x i =?, 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+s P E+t P E), where s P is the maximal size of a minterm of P(x) and t P ‘is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask Ω(s P E+t P E) queries for some input.