In this paper, a necessary and sufficient condition for satisfiability of a boolean formula, in CNF, has been determined. It has been found that the maximum cardinality of satisfiable boolean formula increases exponentially, with increase in number of variables. Due to which, any algorithm require exponential time, in worst case scenario, depending upon the number of variables in a boolean formula, to check satisfiability of the given boolean formula. Which proves the non-existence of a polynomial time algorithm for satisfiability problem. As satisfiability is a NP-complete problem, and non-existence of a polynomial time algorithm to solve satisfiability proves exclusion of satisfiability from class P. Which implies P is not equal to NP. Further, the necessary and sufficient condition can be used to optimize existing algorithms, in some cases, the unsatisfiability of a given boolean function can be determined in polynomial time. For this purpose, a novel function has been defined, that can be used to determine cardinality of a given boolean formula, and occurances of a literal in the given formula, in polynomial time.
翻译:在本文中,已经确定了CNF中布尔式配方的相对性的一个必要和充分的条件。已经发现,可作匹比布布林式配方的最大基本性随着变数的增加而成倍增长。因此,在最坏的情况下,任何算法都需要指数时间,这取决于布林式配方中变量的数量,以检查给定布林式配方的相对性。这证明不存在关于可作比性问题的多元时算法。由于可作比对性是一个NP问题,而且不存在用于解决可作比性的多元时算法,这就证明P类的可作比喻性被排除在外。这意味着P类不等于NP。此外,可以使用必要和充分的条件来优化现有的算法,在某些情况下,特定布林式函数的不适应性可以在多元性时间中确定。为此,已经定义了一个新功能,可以用来确定给定布林式配方的公式和发生式的基数。