On the Tractability of Un/Satisfiability

EasyChair Preprint 1734, version 3

Abstract

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 the 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. As a result, the formula is satisfied iff the scope of every literal is true.

Keyphrases: NP-complete, P vs NP, X3SAT, one-in-three SAT

@booklet{EasyChair:1734,
  author    = {Latif Salum},
  title     = {On the Tractability of Un/Satisfiability},
  howpublished = {EasyChair Preprint 1734},
  year      = {EasyChair, 2020}}