布尔函数判定树复杂性的理论与方法-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

布尔函数判定树复杂性的理论与方法

项目名称：布尔函数判定树复杂性的理论与方法
项目类别：面上项目
批准号：10671204
申请代码：A011503
项目来源：国家自然科学基金
研究期限：2007-01-01-2009-12-31

项目负责人：高随祥
负责人职称：教授
依托单位：中国科学院大学
批准年度：2006

中文摘要：

布尔函数判定树是一种基本的计算模型，判定树复杂性是一种重要的计算复杂性类别。本项目研究了布尔函数的判定树复杂性，探讨了解决著名的Rivest-Vuillemin猜想和Karp猜想的可能途径；引入一种Galois域对图的Hamilton性质进行了研究；证明了非平凡单调二部有向图性质的隐匿性；证明了前人提出的一种拓扑拓展方法研究布尔函数隐匿性的不可行性；在利用置换群方法和代数拓扑途径研究布尔函数和图性质的判定树复杂性方面取得了一些新的结果。本项目对解决判定树复杂性的Rivest-Vullemin猜想和Karp猜想进行了有益的探索，虽然未能最终解决这两个困难的猜想，但在研究中获得的进展和经验对后续研究有重要的借鉴作用。

中文主题词：布尔函数；图性质；计算复杂性；Karp猜想；Rivest-Vullemin猜想

结论摘要：

英文主题词Boolean function; graph property; computational complexity; Karp conjecture; Rivest-Vuillemin conjecture

成果综合统计