کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427213 | 686470 | 2013 | 8 صفحه PDF | دانلود رایگان |
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(ε−2⋅1.51426n)O(ε−2⋅1.51426n), for #4-SAT, it runs in time O(ε−2⋅1.60816n)O(ε−2⋅1.60816n), with error bound ε.
► We provide the currently fastest randomized approximation scheme for #k-SAT.
► We identify maximal independent substructures of the input formula.
► We reduce the search space using the maximal independent substructures considerably.
► Our approximation scheme works for any k.
Journal: Information Processing Letters - Volume 113, Issue 9, 15 May 2013, Pages 337–344