The Boolean SATisfiability Problem and the orthogonal group $O(n)$

Abstract

We explore the relations between the Boolean Satisfiability Problem with $n$ Boolean variables and the orthogonal group $\mbox{O}(n)$. We show that all $2^n$ possible solutions induce involutions of ${\mathbb{R}}^n$ that lie in the compact, disconnected real manifold of dimension $n(n-1)/2$ of $\mbox{O}(n)$. This result in turn gives a new unsatisfiability test within group $\mbox{O}(n)$.

13 pages, no figures, 7 references

References in corpus (2)

• On Spinors Transformations
• The Boolean SATisfiability Problem in Clifford algebra

Cited by in corpus (2)

• On Simple Spinors, Null Vectors and the Orthogonal Group O(n)
• The Clifford algebra of $R^{n,n}$ and the Boolean Satisfiability Problem