The relative exponential time complexity of approximate counting satisfying assignments

Autoren Patrick Traxler
Editoren
Titel The relative exponential time complexity of approximate counting satisfying assignments
Buchtitel IPEC 2014 - 9th International Symposium on Parameterized and Exact Computation, Breslau, Polen, September 10-12, 2014
Typ sonst
Veröffentlichungstyp Extended Abstract
Monat September
Jahr 2014
SCCH ID# 1451
Abstract

We study the exponential time complexity of approximate counting satisfying assignments of CNFs. We reduce the problem to deciding satis_ability of a CNF. Our reduction preserves the number of variables of the input formula and thus also preserves the exponential complexity of approximate counting. Our algorithm is also similar to an algorithm which works particular well in practice and for which no approximation guarantee is known.