摘要
本文考虑具有优先代表资格的NP完全问题的对偶问题——析取范式永真性判定问题.本文从构造的角度对析取范式作了分析,得出了如下结果:在由n个确定的命题变元所可能构成的一切不含均覆盖的析取范式中,含有三角式的析取范式占绝大多数.基于这个结果,本文得出了一个求解析取范式永真性判定问题的近似快速算法.
Considering the decision problem for validity of DNF,the following result is obtained by analysing the problem from the constructive view point:Among all DNFs without any equal covering generated by composing n definite proposition variables,those with property o easy decision,that is those having triangular forms,are in the most majority.Based on the above result,an approximately fast algorithm is obtained for the decision problem of DNF validity.
出处
《计算机学报》
EI
CSCD
北大核心
1994年第5期384-387,共4页
Chinese Journal of Computers
基金
国家自然科学基金
关键词
析取范式
算法
均覆盖
Disjunctive normal form(DNF)
NP-complete problem
algorithm
equal covering
triangular form.