ICCA2020:P000117

The Clifford algebra of $R^{n,n}$ and the Boolean SATisfiability Problem

*Marco Budinich (University of Trieste and INFN, Italy)

%% ABSTRACT template
%% 12th ICCA, Aveiro

\documentclass[9pt]{amsart}
%
\usepackage{amsfonts,amsthm,amssymb,amsmath}
\usepackage[scale={0.8,0.9}, a4paper, nofoot, bindingoffset=1cm]{geometry}
\parindent0mm
\parskip0mm
\sloppy
%
\newtheorem*{theorem}{Theorem}
%
\newcommand{\ICCAabstract}[5]{{\bf #1}\par\medskip{\sc #2}\\{#4}\\{\tt #3}
\par\bigskip {#5}\bigskip\bigskip}
%
\begin{document}
\begin{twocolumn}
%
% Please do not change ANYTHING outside the following latex command and do NOT use 
% any hard font commands inside the command options (as \bf, \sf, \large etc.) except \empf{} if 
% you want to emphasise something. Please do not use labels and reference to formula numbers
% in your abstract (as this will cause problems in the production process). You may use the 
% \begin{theorem} \end{theorem} environment to state theorems, use all font commands and 
% symbols provided by {amsfonts} and {amssymb} packages INSIDE formulae.  
% Please do NOT give references in or after your abstract.
%
% If your abstract exceeds 300 words in length, we will cut it after 300 words and replace 
% the remainder by \dots
%
\ICCAabstract%
{%Title of Talk	
 The Clifford algebra of $R^{n,n}$ and the Boolean SATisfiability Problem
}
{% Name
Marco Budinich
}
{% Email Address
mbh@ts.infn.it
}
{% Address, NO LINE BREAKS
University of Trieste and INFN, Trieste, Italy 
}
{% Abstract 
% NOT TO EXCEED 300 WORDS
We show that the Boolean SATisfiability Problem with $n$ literals has a simple formulation in the Clifford algebra of neutral space $R^{n,n}$. In this setting there is a natural bijection between the $2^n$ simple spinors forming the Fock basis of the spinor space of the algebra and the possible assignments of the $n$ Boolean literals, the Boolean atoms. Moreover any of these simple spinors is the representative element of a partition of the group O$(n)$ into $2^n$ equivalence classes that, in a nutshell, are the ``fundamental'' involutions of $R^{n}$. In this way the combinatorial Boolean SATisfiability Problem can be attacked in the continuous group O$(n)$ rather that in a discrete set with $2^n$ elements. We argue that, being O$(n)$ a smooth compact manifold of dimension $n (n-1) / 2$, this offers some advantages.
} 
%
\end{twocolumn}
\end{document}

%% ABSTRACT template %% 12th ICCA, Aveiro \documentclass[9pt]{amsart} % \usepackage{amsfonts,amsthm,amssymb,amsmath} \usepackage[scale={0.8,0.9}, a4paper, nofoot, bindingoffset=1cm]{geometry} \parindent0mm \parskip0mm \sloppy % \newtheorem*{theorem}{Theorem} % \newcommand{\ICCAabstract}[5]{{\bf #1}\par\medskip{\sc #2}\\{#4}\\{\tt #3} \par\bigskip {#5}\bigskip\bigskip} % \begin{document} \begin{twocolumn} % % Please do not change ANYTHING outside the following latex command and do NOT use % any hard font commands inside the command options (as \bf, \sf, \large etc.) except \empf{} if % you want to emphasise something. Please do not use labels and reference to formula numbers % in your abstract (as this will cause problems in the production process). You may use the % \begin{theorem} \end{theorem} environment to state theorems, use all font commands and % symbols provided by {amsfonts} and {amssymb} packages INSIDE formulae. % Please do NOT give references in or after your abstract. % % If your abstract exceeds 300 words in length, we will cut it after 300 words and replace % the remainder by \dots % \ICCAabstract% {%Title of Talk The Clifford algebra of $R^{n,n}$ and the Boolean SATisfiability Problem } {% Name Marco Budinich } {% Email Address mbh@ts.infn.it } {% Address, NO LINE BREAKS University of Trieste and INFN, Trieste, Italy } {% Abstract % NOT TO EXCEED 300 WORDS We show that the Boolean SATisfiability Problem with $n$ literals has a simple formulation in the Clifford algebra of neutral space $R^{n,n}$. In this setting there is a natural bijection between the $2^n$ simple spinors forming the Fock basis of the spinor space of the algebra and the possible assignments of the $n$ Boolean literals, the Boolean atoms. Moreover any of these simple spinors is the representative element of a partition of the group O$(n)$ into $2^n$ equivalence classes that, in a nutshell, are the ``fundamental'' involutions of $R^{n}$. In this way the combinatorial Boolean SATisfiability Problem can be attacked in the continuous group O$(n)$ rather that in a discrete set with $2^n$ elements. We argue that, being O$(n)$ a smooth compact manifold of dimension $n (n-1) / 2$, this offers some advantages. } % \end{twocolumn} \end{document}

The 12th International Conference on Clifford Algebras and Their Applications in Mathematical Physics

The Clifford algebra of $R^{n,n}$ and the Boolean SATisfiability Problem