Download PDFOpen PDF in browser

On the Tractability of Un/Satisfiability

EasyChair Preprint no. 1734, version 3

Versions: 123history
12 pagesDate: April 7, 2020


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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Latif Salum},
  title = {On the Tractability of Un/Satisfiability},
  howpublished = {EasyChair Preprint no. 1734},

  year = {EasyChair, 2020}}
Download PDFOpen PDF in browser