Statistical mechanics of an NP-complete problem: subset sum

DOI10.1088/0305-4470/34/44/314MaRDI QIDQ4533606zbMATH OpenOpenAlexFDO

Authors Tomohiro Sasamoto, Taro Toyoizumi, Hidetoshi Nishimori

Publication date 11 June 2002

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0106125

zbMATH Keywords

NP-complete problemnumber partitioning problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Equilibrium statistical mechanics (82B99)

Abstract: We study statistical properties of an NP-complete problem, the subset sum, using the methods and concepts of statistical mechanics. The problem is a generalization of the number partitioning problem, which is also an NP-complete problem and has been studied in the physics literature. The asymptotic expressions for the number of solutions are obtained. These results applied to the number partitioning problem as a special case are compared with those which were previously obtained by a different method. We discuss the limit of applicability of the techniques of statistical mechanics to the present problem.

Recommendations

• Phase Transition in the Number Partitioning Problem
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• A physicist's approach to number partitioning
• Phase transitions of subset sum and Shannon's limit in source coding
• Statistical mechanics of the knapsack problem

Cited in

(6)

• Phase transitions of subset sum and Shannon's limit in source coding
• Some combinatorial problems in statistical physics
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• Proof of the local REM conjecture for number partitioning. I: Constant energy scales
• Phase Transition in the Number Partitioning Problem
• Statistical mechanics of the knapsack problem

This page was built for publication: Statistical mechanics of an NP-complete problem: subset sum

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