Renyi entropies as a measure of the complexity of counting problems

    Authors

    C. Chamon;E. R. Mucciolo

    Comments

    Authors: contact us about adding a copy of your work at [email protected]

    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
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.