The Boolean SATisfiability Problem in Clifford algebra

Abstract

We present a formulation of the Boolean Satisfiability Problem in spinor language that allows to give a necessary and sufficient condition for unsatisfiability. With this result we outline an algorithm to test for unsatisfiability with possibly interesting theoretical properties.

16 pages, better formalization and simpler proofs

References in corpus (2)

• Survey propagation: an algorithm for satisfiability
• On Spinors Transformations

Cited by in corpus (2)

• The Boolean SATisfiability Problem and the orthogonal group $O(n)$
• The Clifford algebra of $R^{n,n}$ and the Boolean Satisfiability Problem