pipette
ESEspañol

A Study in Solution Models for SAT using the PBNF-transform

Pelle Brooke Borgeke

PreprintBold claims, read critically

In the authors' words

In this article, we use the PBNF-transform, or Polynomial Boolean Normal Form, described earlier in two articles and now extended to higher arity, to solve Boolean satisfiability problems (SAT), which are part of the P versus NP problem. SAT consists of a statement of conjunctions of clauses, and in our SAT-solving models, we dualize the logical equations, inverting the problem by multiplying letters (literals) in the transferred clauses, now phrases: , and using a binary iterated composition based on adding polynomials for the conjunctions in our solution formula. We obtain Polynomial Boolean Equations, PBE=0, by also renaming the truth value (T). To find a solution, we look for repeating literals in the clauses to factor out. With reversed literal repetition, we can even reduce the CNF to the sum of the transformed clauses.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.