| On Decision Tree Complexity of Boolean Function and Yao's Question |
| Received:October 19, 1999 |
| Key Words:
Boolean function decision tree complexity Rivest-Vuillemin conjecture.
|
| Fund Project:Supported by the National Natural Science Foundation of China (10171095), Foundation of Chinese Academy of Science (J2001), and Foundation of GSCAS(yzjj200105) |
|
| Hits: 2462 |
| Download times: 1372 |
| Abstract: |
| A Boolean function f(x1,x2,…,xn) 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 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. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2002.04.005 |
| View Full Text View/Add Comment |
