A physicist's approach to number partitioning
arXiv:cond-mat/0009230
Abstract
The statistical physics approach to the number partioning problem, a classical NP-hard problem, is both simple and rewarding. Very basic notions and methods from statistical mechanics are enough to obtain analytical results for the phase boundary that separates the ``easy-to-solve'' from the ``hard-to-solve'' phase of the NPP as well as for the probability distributions of the optimal and sub-optimal solutions. In addition, it can be shown that solving a number partioning problem of size to some extent corresponds to locating the minimum in an unsorted list of $\bigo{2^N}$ numbers. Considering this correspondence it is not surprising that known heuristics for the partitioning problem are not significantly better than simple random search.
35 pages, to appear in J. Theor. Comp. Science, typo corrected in eq.14
References in corpus (4)
Cited by in corpus (16)
- Adiabatic Quantum Computing
- What is the Computational Value of Finite Range Tunneling?
- Extreme Value Statistics and Traveling Fronts: Various Applications
- Why glass elasticity affects the thermodynamics and fragility of super-cooled liquids
- The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
- On the Dynamics of Glassy Systems
- Efficient exploration of discrete energy landscapes
- Local energy statistics in disordered systems: a proof of the local REM conjecture
- Microscopic realizations of the Trap Model
- Ordinal Maximin Share Approximation for Goods
- Dynamic phase diagram of the Number Partitioning Problem
- Computational Complexity for Physicists
- Subset sum phase transitions and data compression
- Phase transition in the Countdown problem
- Phase transitions in Number Theory: from the Birthday Problem to Sidon Sets
- A p-Spin Interaction Ashkin-Teller Spin-Glass Model