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

DOI10.1088/1742-5468/2013/04/P04008zbMath1456.82705arXiv1302.2826OpenAlexW2027034364MaRDI QIDQ3301573

Eduardo R. Mucciolo, Claudio Chamon

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)

Related Items (2)

Information-theoretic measures for a position-dependent mass system in an infinite potential well ⋮ Tensor network contractions for \#SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Random generation of combinatorial structures from a uniform distribution
• Counting models for 2SAT and 3SAT formulae
• The Complexity of Enumeration and Reliability Problems
• Entropy of theK-Satisfiability Problem
• Computational Complexity
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications

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