By creating some new concepts and methods: checking tree, long unit path, direct contradiction unit pair, indirect contradiction unit pair, additional contradiction unit pair, 2-unit layer and 3-unit layer, redundant units, and destroying parallel pairs , we successfully transform solving a 3SAT problem to solving 2SAT problems in polynomial time. Thus we proved that NP=P.
翻译:通过引入若干新概念与方法:检查树、长单元路径、直接矛盾单元对、间接矛盾单元对、附加矛盾单元对、2-单元层与3-单元层、冗余单元以及破坏平行对,我们成功将3SAT问题的求解转化为在多项式时间内求解2SAT问题。由此我们证明了NP=P。