Title

Renyi entropies as a measure of the complexity of counting problems

Authors

Authors

C. Chamon;E. R. Mucciolo

Comments

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

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

WOS:000317463900010

ISSN

1742-5468

Share

COinS