Can I read Proving unsatisfiability of CNFs locally on EtoBox?

Proving unsatisfiability of CNFs locally by Eugene Goldberg is a Computer Science article available to read on EtoBox.

What is Proving unsatisfiability of CNFs locally about?

We i n troduce a new method for checking satis ability 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 unsatis able. (The 1neighborhood 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 unsatis ability without generating an empty clause. The reason for avoiding the generation of an empty clause is that we believe that no deterministic algorithm can e ciently 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 i n troduce 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.

Who reads Proving unsatisfiability of CNFs locally?

Author

Eugene Goldberg

Publisher

Elsevier Science; Elsevier ; Elsevier BV; Amsterdam: Elsevier BV (ISSN 1571-0653)

Published

2001

Language

EN

Field

Computer Science (Physical Sciences)