On the Tractability of Un/Satisfiability

EasyChair Preprint no. 1734, version 1

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, one-in-three SAT, P vs NP, X3SAT

@Booklet{EasyChair:1734,
  author = {Latif Salum},
  title = {On the Tractability of Un/Satisfiability},
  howpublished = {EasyChair Preprint no. 1734},

  year = {EasyChair, 2019}}