• Title of article

    Proving unsatisfiability of CNFs locally

  • Author/Authors

    Goldberg، نويسنده , , Eugene، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2001
  • Pages
    19
  • From page
    96
  • To page
    114
  • Abstract
    We introduce a new method for checking satisfiability of Conjunctive Normal Forms (CNFs). The method is based on the fact that if no clause of a CNF contains a satisfying assignment in its 1-neighborhood, then this CNF is unsatisfiable. (The 1-neighborhood of a clause is the set of all assignments satisfying only one literal of this clause). The idea of 1-neighborhood exploration allows one to prove unsatisfiability without generating an empty clause. The reason for avoiding the generation of an empty clause is that we believe that no deterministic algorithm can efficiently reach a global goal (deducing an empty clause) using an inherently local operation (resolution). At the same time when using 1-neighborhood exploration a global goal is replaced with a set of local subgoals, which makes it possible to optimize local steps of the proof. We introduce two proof systems formalizing 1-neighborhood exploration. An interesting open question is if there exists a class of CNFs for which the introduced systems have proofs that are exponentially shorter than the ones that can be obtained by general resolution.
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Serial Year
    2001
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Record number

    1453228