Renyi entropies as a measure of the complexity of counting problems

Claudio Chamon, Eduardo R. Mucciolo

Counting problems such as determining how many bit strings satisfy a given Boolean logic formula are notoriously hard. In many cases, even getting an approximate count is difficult…