Exploiting Independent Subformulas: A Faster Approximation Scheme for #k-SAT

Schmitt M, Wanka R (2013)

Publication Type: Journal article

Publication year: 2013

Journal

Information Processing Letters Elsevier

Publisher: Elsevier

Book Volume: 113

Pages Range: 337-344

DOI: 10.1016/j.ipl.2013.02.013

Abstract

We present an improvement on Thurley's recent randomized approximation scheme for #k-SAT where the task is to count the number of satisfying truth assignments of a Boolean function Φ given as an n-variable k-CNF. We introduce a novel way to identify independent substructures of Φ and can therefore reduce the size of the search space considerably. Our randomized algorithm works for any k. For #3-SAT, it runs in time O(ε- ²×1.51426ⁿ), for #4-SAT, it runs in time O(ε-²×1.60816ⁿ), with error bound ε. © 2013 Elsevier B.V. All rights reserved.

Authors with CRIS profile

Berthold Immanuel Schmitt Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung) Rolf Wanka Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

How to cite

APA:

Schmitt, M., & Wanka, R. (2013). Exploiting Independent Subformulas: A Faster Approximation Scheme for #k-SAT. Information Processing Letters, 113, 337-344. https://dx.doi.org/10.1016/j.ipl.2013.02.013

MLA:

Schmitt, Manuel, and Rolf Wanka. "Exploiting Independent Subformulas: A Faster Approximation Scheme for #k-SAT." Information Processing Letters 113 (2013): 337-344.

BibTeX: Download