论文部分内容阅读
NP完全问题是一类在计算复杂性理论中被证明为较难求解的问题,这类问题中包含有很多在理论和实际中很有意义的问题。NP完全问题中的一个问题的对偶问题若存在快速(多项式意义下)的求解算法,则所有NP完全问题都有快速的求解算法。但目前人们还没有找到一个求解NP完全问题的真正快速算法,并且有迹象表明求解NP完全问题的真正快速算法是不存在的。本文针对一个典型的NP完全问题的对偶问题——析取范式永真性
The NP-complete problem is a type of problem proven to be difficult to solve in computational complexity theory. There are many problems that are of great theoretical and practical significance. The Dual Problem of a Problem in NP Complete Problem If there is a fast (polynomial) solution algorithm, then all NP-complete problems have fast solution algorithms. But so far a real fast algorithm for solving NP-complete problems has not yet been found, and there is no indication that a true fast algorithm for solving NP-complete problems does not exist. In this paper, we deal with the dual problem of a typical NP complete problem - disjunctive normality