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
Typ Artikel
Journal Algorithmica (Special Issue IPEC 2014)
Nummer 2
Band 75
DOI 10.1007/s00453-016-0134-y
Monat June
Jahr 2016
Seiten 339-362
SCCH ID# 16082
Abstract

We study the exponential time complexity of approximate counting satisfying assignments of CNFs. We reduce the problem to deciding satisfiability 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 particularly well in practice and for which no approximation guarantee is known.