摘要
我们考虑具有优先代表资格的NP完全问题——析取范式的永真性判定问题。本文从全局性构造的角度对它作了某种分析,得出如下结果:在由n个确定的命题变元所可能构成的一切析取范式中,永真析取范式的个数与非永真析取范式的个数之比当n趋于无穷时为无穷大。 基于所得结果,对于析取范式永真性判定问题得出了一个近似快速的求解算法,按此算法,对绝大多数的析取范式,其永真性问题,在多项式时间内都可解决。
We consider the NP complete problem with superior representative qualification——the decision for the validity of DNF. This paper analyses the problem from the viewpoint of global construction and obtains the following results: In all DNF generated by composing n definite proposition variables, the ratio of the number of valid DNF to that of nonvalid DNF tends to infinite as n→∞. Based on the above results, an approximate fast algorithm is obtained for the decision problem of DNF validity. Using this algorithm, most DNF validity problems can be solved in polynomial time.
出处
《计算机学报》
EI
CSCD
北大核心
1989年第2期148-152,共5页
Chinese Journal of Computers
基金
国家自然科学基金
