Rényi entropies as a measure of the complexity of counting problems

DOI10.1088/1742-5468/2013/04/P04008MaRDI QIDQ3301573zbMATH OpenOpenAlexFDO

Authors Claudio Chamon, Eduardo R. Mucciolo

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2826

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Exactly solvable dynamic models in time-dependent statistical mechanics (82C23)

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 ightarrow 0) provides information about the difficulty of counting solutions exactly, while S(q>0) indicates the possibility of doing 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 approximate efficient algorithms are known for this problem. However, for the negated (disjunctive) form of the problem, S(q ightarrow 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 suggests that efficient algorithms for the conjunctive normal form may not exist.

Recommendations

• Difficult instances of the counting problem for 2-quantum-SAT are very atypical
• Quantum algorithm for SAT problem andquantum mutual entropy
• scientific article; zbMATH DE number 1670534
• Complexity of generalized satisfiability counting problems
• Counting solutions to random CNF formulas

Cites work

• scientific article; zbMATH DE number 3173999 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• A threshold for unsatisfiability
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Computational Complexity
• Counting models for 2SAT and 3SAT formulae
• Entropy of theK-Satisfiability Problem
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Enumeration and Reliability Problems
• The complexity of counting problems

Cited in

(3)

• Information-theoretic measures for a position-dependent mass system in an infinite potential well
• Tensor network contractions for \#SAT
• scientific article; zbMATH DE number 431873 (Why is no real title available?)

This page was built for publication: Rényi entropies as a measure of the complexity of counting problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301573)