This paper shows effectiveness of X3SAT in proving P = NP. This is due to the fact that it is easy to check unsatisfiability of a particular truth assignment. A truth assignment leads to some reductions of clauses by means of "exactly-1 disjunction". The reductions result in a conjunction of literals, called the scope of the assignment. It is proved that this particular truth assignment makes the formula unsatisfiable iff the scope_s is unsatisfiable for some s, which is trivial to check. Then, each literal such that its scope is unsatisfiable is removed from the formula. Therefore, the formula is satisfiable iff the scope of every literal is satisfied.
翻译：本文显示了 X3SAT 证明 P = NP 的有效性 。 这是因为很容易检查特定真相任务不满意的情况。 真相任务通过“ 绝对-1 分离” 的方式导致某些条款的减少。 减少的结果是一连串的字面, 称为任务范围。 事实证明, 特定真相任务使得公式无法满足, 如果范围_ s 对某些公式来说是不满意的, 这一点是微不足道的。 然后, 每一个字句中如果其范围不满意, 就会从公式中删除。 因此, 如果满足了每个字行的范围, 公式是可以令人信服的 。
相关内容
微信扫码咨询专知VIP会员