Title

Rényi Entropies As A Measure Of The Complexity Of Counting Problems

Keywords

typical-case computational complexity

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 Rényi 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 Rényi 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. © 2013 IOP Publishing Ltd and SISSA Medialab srl.

Publication Date

4-1-2013

Publication Title

Journal of Statistical Mechanics: Theory and Experiment

Volume

2013

Issue

4

Number of Pages

-

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1088/1742-5468/2013/04/P04008

Socpus ID

84876887519 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84876887519

This document is currently not available here.

Share

COinS