#### Title

Renyi entropies as a measure of the complexity of counting problems

#### Abbreviated Journal Title

J. Stat. Mech.-Theory Exp.

#### Keywords

typical-case computational complexity; Mechanics; Physics, Mathematical

#### Abstract

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. Here we propose that entanglement, a common concept in quantum information theory, may serve as a telltale of the difficulty of counting exactly or approximately. We quantify entanglement by using Renyi entropies S-(q), which we define by bipartitioning the logic variables of a generic satisfiability problem. We conjecture that S-(q -> 0) provides information about the difficulty of counting solutions exactly, while S-(q>0) indicates the possibility of carrying out an efficient approximate counting. We test this conjecture by employing a matrix computing scheme to numerically solve #2SAT problems for a large number of uniformly distributed instances. We find that all Renyi entropies scale linearly with the number of variables in the case of the #2SAT problem; this is consistent with the fact that neither exact nor efficient approximate algorithms are known for this problem. However, for the negated (disjunctive) form of the problem, S-(q -> 0) scales linearly while S-(q>0) tends to zero when the number of variables is large. These results are consistent with the existence of fully polynomial-time randomized approximate algorithms for counting solutions of disjunctive normal forms and suggest that efficient algorithms for the conjunctive normal form may not exist.

#### Journal Title

Journal of Statistical Mechanics-Theory and Experiment

#### Publication Date

1-1-2013

#### Document Type

Article

#### Language

English

#### First Page

13

#### WOS Identifier

#### ISSN

1742-5468

#### Recommended Citation

"Renyi entropies as a measure of the complexity of counting problems" (2013). *Faculty Bibliography 2010s*. 3772.

http://stars.library.ucf.edu/facultybib2010/3772

## Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu