布尔函数的判定树复杂性及问题(英文)

摘要

设f（x1,x2,…,xn）是一个布尔函数。如果计算f（x1,x2,…,xn）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x1,x2,…,xn）在循环群Cm×Cn的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持著名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.