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

On Decision Tree Complexity of Boolean Function and Yao's Question

英文关键词:Boolean function  decision tree  complexity  Rivest-Vuillemin conjecture.

中文摘要:

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

英文摘要:

      A Boolean function f(x₁,x₂,…,x_n) is said to be elusive, if every decision tree algorithm computing f must examine all n variables in the worst case. In 1988, A.C.C. Yao introduced a question: Is any nontrivial monotone Boolean function that is invariant under the transitive act of group C_m×C_n elusive? The positive answer to this question supports the famous Rivest-Vuillemin conjecture on decision tree complexity. In this paper, we shall partly answer this question.