  We present a novel application of the Kramers-Wannier duality on one of the
most important problems of computer science, the Boolean satisfiability problem
(SAT). More specifically, we focus on sharp-SAT or equivalently #SAT - the
problem of counting the number of solutions to a Boolean satisfaction formula.
#SAT can be cast into a statistical-mechanical language, where it reduces to
calculating the partition function of an Ising spin Hamiltonian with multi-spin
interactions. We show that Kramers-Wannier duality can be generalized to apply
to such multi-connected spin networks. We present an exact dual partner to #SAT
and explicitly verify their equivalence with a few simple examples. It is shown
that the NP-completeness of the original problem maps on the complexity of the
dual problem of enumerating the number of non-negative solutions to a
Diophantine system of equations. We discuss the implications of this duality
and the prospects of similar dualities applied to computer science problems.
