A Boolean function /(x1,x2,…,xn) is said to be elusive, if every decision tree algorithm computing / must examine all n variables in the worst case. In 1988, A.C.C. Yao introduced a question: Is any nontrivial monoto...A Boolean function /(x1,x2,…,xn) is said to be elusive, if every decision tree algorithm computing / 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 Cm × Cn 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.展开更多
基金Supported by the National Natural Science Foundation of China (10171095) Foundation of Chinese Academy of Science (J2001), and Foundation of GSCAS
文摘A Boolean function /(x1,x2,…,xn) is said to be elusive, if every decision tree algorithm computing / 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 Cm × Cn 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.
