CNF中布利安公式的可满足性及其对P与NP问题的影响的必要和充分条件 (Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and its Implications on P versus NP problem)

from arxiv, Second Revision: 17 Pages, Affiliation and email address of author added, elaborated Optimisations section, refined theorem 10.8, references updated, typing errors corrected Third Revision: 22 pages, complexity calculated on instance size, results changed, algorithm and related sections added

Boolean satisfiability problem has applications in various fields. An efficient algorithm to solve satisfiability problem can be used to solve many other problems efficiently. The input of satisfiability problem is a finite set of clauses. In this paper, properties of clauses have been studied. A type of clauses have been defined, called fully populated clauses, which contains each variable exactly once. A relationship between two unequal fully populated clauses has been defined, called sibling clauses. It has been found that, if one fully populated clause is false, for a truth assignment, then all it's sibling clauses will be true for the same truth assignment. Which leads to the necessary and sufficient condition for satisfiability of a boolean formula, in CNF. The necessary and sufficient condition has been used to develop a novel algorithm to solve boolean satisfiability problem in polynomial time, which implies, P equals NP. Further, some optimisations have been provided that can be integrated with the algorithm for better performance.

翻译：Boolean 相容性问题在多个领域都有应用。解决相容性问题的有效算法可以有效地用于解决许多其他问题。相容性问题的输入是一组有限的条款。在本文中, 已经研究了条款的属性。已经定义了一类条款, 称为完全包含所有条款, 其中每个变量都只包含一次。已经定义了两个不均匀的全称条款之间的关系, 称为sibling 条款。已经发现, 如果一个完全覆盖的条款是虚假的, 对于一个真相分配来说, 那么它的所有比喻条款都将适用于同一的真相分配。这导致一个布林公式在CNF中具有必要和充分性的条件。已经使用了一种必要和充分的条件来开发一种新颖的算法, 以解决多瑙河时间的布林相容性问题, 这意味着, P 等NP。此外, 已经提供了一些选择性, 能够与更佳性表现的算法结合起来。