摘要
P=?NP问题是计算复杂性中至今仍未解决的著名难题。这个问题的正面回答等价于有效算法判断析取范式的永真性。显然,寻找一个有效算法对解决这一问题是很有意义的。本文在文献[1]的基础上,就寻找判断析取范式快的算法作了若干初步研究．主要成果有定理1,2,3,4,5,6。此结果为寻找快的有效算法奠定了理论基础。最后巧妙地借助补关系图的概念,给出算法2．1及打破闭残的扩展树算法3.1。
In this paper, based on document [1], we have got Theorem 1, 2, 3, 4, 5, 6, they are theoretical fundation for finding efficieat algorithm.Finally, we construct divide -conquer algorithm 2.1 and give a developed algorithm 3.1 for broking close - incomplete.
出处
《黑龙江大学自然科学学报》
CAS
1992年第4期54-59,共6页
Journal of Natural Science of Heilongjiang University
关键词
子句集
析取范式
计算复杂性
Clause set
disjunctive normal form
huge item
complementary relation -graph
algorithm of developed tree
