欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
位置：立项数据库 > 立项详情页
中文摘要：
本项目研究成果主要包括(1) 特殊结构命题公式类的性质及判定问题。系统地研究了著名难例鸽巢公式的若干结构性质，找到了最大可满足指派的两种标准范式。如果允许对同构公式的结点使用剪枝规则，给出了在三次方时间内对鸽巢公式不可满足性验证的算法。研究了CNF公式的Horn子结构对公式本身可满足性的影响，引入最大可改名Horn子结构与最小不可嵌入Horn子结构两种方法研究CNF公式的可满足性。给出了将CNF公式类多项式时间归约到规则结构类的技术，为在规则结构下研究SAT问题提供了理论基础。（2）利用特殊变元集（关键文字集、后门集）研究CNF公式的可满足性和有效推理，提出了特殊变元集的计算方法，研究了关键文字集与极小不可满足公式之间的内在联系，应用特殊变集的特殊性设计求解SAT问题的算法。研究了信息传播算法在特殊变元集计算中的应用、以及信息传传播算法算法的收敛性。（3）给出了二元关系性质测试算法和复杂性分析，深入研究了布尔函数的学习与性质测试的理论，其理论和方法可以用到机器学习的算法理论、协调检测理论和算法设计。
结论摘要：
英文主题词propositional formula,The sets of sepcial variables,structure property,algorithm design,information passing algorithm,test and analysis of properties.
成果综合统计
期刊论文
会议论文
专利
获奖
著作
期刊论文
相关项目
许道云的项目
