| 布尔函数的判定树复杂性及问题 |
| |
| 引用本文： | 高随祥,杨德庄. 布尔函数的判定树复杂性及问题[J]. 数学研究及应用, 2002, 22(4): 531-537 |
| |
| 作者姓名： | 高随祥 杨德庄 |
| |
| 作者单位： | 中国科学院研究生数学部,华罗庚应用数学与信息科学研究中心,北京,100039 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China (10171095)，Foundation of Chinese Academy of Science (J2001), and Foundation of GSCAS |
| |
| 摘 要： | 设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猜想.本文将部分地解答这一问题.
|
| 关 键 词： | 判定树算法 布尔函数 复杂性 |
| 收稿时间： | 1999-10-19 |
On Decision Tree Complexity of Boolean Function and Yao''s Question |
| |
| GAO Sui-xiang and YANG De-zhuang. On Decision Tree Complexity of Boolean Function and Yao''s Question[J]. Journal of Mathematical Research with Applications, 2002, 22(4): 531-537 |
| |
| Authors: | GAO Sui-xiang and YANG De-zhuang |
| |
| Affiliation: | Math. Dept.; Graduate School of the Chinese Academy of Sciences; Hua Look-Keng Inst. of Appl. Math; & Info. Sci.; Beijing; China;Math. Dept.; Graduate School of the Chinese Academy of Sciences; Hua Look-Keng Inst. of Appl. Math; & Info. Sci.; Beijing; China |
| |
| Abstract: | A Boolean function f(x1, x2,……, xn) is said to be elusive, if every decisiontree algorithm computing f must exanfine all n variables in the worst case. In 1988,A.C.C. Yao introduced a question: Is any nontrivial monotone Boolean function that isinvariant under the transitive act of group Cm × Cn elusive? The positive answer to thisquestion supiorts the famous Rivest-Vnillemin conjecture on decision tree complexity.In this paper, we shall partly answer this question. |
| |
| Keywords: | Boolean function decision tree complexity Rivest-Vuillemin conjecture. |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
|
点击此处可从《数学研究及应用》下载免费的PDF全文 |
|
