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

DOI10.1088/1742-5468/2013/04/P04008zbMATH Open1456.82705arXiv1302.2826OpenAlexW2027034364MaRDI QIDQ3301573FDOQ3301573

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)

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.

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

Recommendations

• Difficult instances of the counting problem for 2-quantum-SAT are very atypical
• Quantum algorithm for SAT problem andquantum mutual entropy
• Publication:2753731
• Complexity of generalized satisfiability counting problems
• Counting solutions to random CNF formulas

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)

Cites Work

• Title not available (Why is that?)
• The complexity of counting problems
• Title not available (Why is that?)
• Computational Complexity
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Enumeration and Reliability Problems
• Counting models for 2SAT and 3SAT formulae
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Title not available (Why is that?)
• A threshold for unsatisfiability
• Entropy of theK-Satisfiability Problem

Cited In (3)

• Information-theoretic measures for a position-dependent mass system in an infinite potential well
• Tensor network contractions for \#SAT
• Title not available (Why is that?)

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)