首页> 外文期刊>Mathematical structures in computer science >NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
【24h】

NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability

机译:NAE决议:一种新的分辨率驳回技术,以证明不是全面的不可起可行性

获取原文
获取原文并翻译 | 示例

摘要

In this paper, we analyze Boolean formulas in conjunctive normal form (CNF) from the perspective ofread-once resolution (ROR) refutation schemes. A read-once (resolution) refutation is one in which eachclause is used at most once. Derived clauses can be used as many times as they are deduced. However,clauses in the original formula can only be used as part of one derivation. It is well known that ROR isnot complete; that is, there exist unsatisfiable formulas for which no ROR exists. Likewise, the problemof checking if a 3CNF formula has a read-once refutation is NP-complete. This paper is concerned witha variant of satisfiability called not-all-equal satisfiability (NAE-satisfiability). A CNF formula is NAEsatisfiableif it has a satisfying assignment in which at least one literal in each clause is set to false. Itis well known that the problem of checking NAE-satisfiability is NP-complete. Clearly, the class of CNFformulas which areNAE-satisfiable is a proper subset of satisfiable CNF formulas. It follows that traditionalresolution cannot always find a proof of NAE-unsatisfiability. Thus, traditional resolution is not a soundprocedure for checking NAE-satisfiability. In this paper, we introduce a variant of resolution called NAEresolutionwhich is a sound and complete procedure for checking NAE-satisfiability in CNF formulas.The focus of this paper is on a variant of NAE-resolution called read-once NAE-resolution in which eachclause (input or derived) can be part of at most one NAE-resolution step. Our principal result is that readonceNAE-resolution is a sound and complete procedure for 2CNF formulas. Furthermore, we providean algorithm to determine the smallest such NAE-resolution in polynomial time. This is in stark contrastto the corresponding problem concerning 2CNF formulas and ROR refutations. We also show that theproblem of checking whether a 3CNF formula has a read-once NAE-resolution is NP-complete.
机译:在本文中,我们从透视中分析了联合正常形式(CNF)的布尔公式读取一次分辨率(ROR)驳回方案。一次性(分辨率)驳斥是其中一个条款最多使用一次。衍生的条款可以使用多次推导出来。然而,原始公式中的子句只能用作一个推导的一部分。众所周知,ROR是不完整;也就是说,存在不存在的不挑离式公式,没有任何ROR存在。同样,问题检查3CNF公式是否具有Read-on Refultion的refulare。本文涉及可称为不相同的可靠性(NAE可满足性)的可满足性的变型。 CNF公式是天瓣的如果它具有令人满意的分配,其中每个子句中的至少一个文字被设置为false。它众所周知,检查NAE可满足性的问题是NP-Treminess。显然,CNF类Arenae可满足的公式是满足CNF公式的适当子集。它遵循传统的决议不能总是找到NAE-INSTASFIALI的证明。因此,传统的分辨率不是声音检查NAE可靠性的程序。在本文中,我们介绍了一种名为Neeresolution的分辨率变种这是在CNF公式中检查NAE可满足性的声音和完整的过程。本文的重点是叫做读取的NAE分辨率的变种,其中每个分辨率条款(输入或衍生)可以是大多数NAE分辨率步骤的一部分。我们的主要结果是ReadonceNAE分辨率是2CNF公式的声音和完整的程序。此外,我们提供一种确定多项式时间中最小这种NAE分辨率的算法。这是耻辱对比关于2CNF公式和ROR反驳的相应问题。我们也表明了检查3CNF公式是否具有读数NAE分辨率的问题是NP-Complete。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号