English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Kramers-Wannier Duality of Statistical Mechanics Applied to the Boolean Satisfiability Problem of Computer Science