Related Experiment Videos
Entropy-based analysis of the number partitioning problem.
A R Lima1, M Argollo de Menezes
1Laboratoire de Physique et Méchanique des Milieux Hétérogènes, ESPCI Paris, 10 rue Vauquelin, 75231 Paris Cedex 05, France. arlima@if.uff.br
Summary
This study applies statistical physics methods to the number partitioning problem (NPP), revealing key differences in spectral degeneracy for generalized versions. These findings may explain the difficulty in solving complex NPP instances.
Area of Science:
- Statistical Physics
- Computer Science
- Computational Complexity
Background:
- The number partitioning problem (NPP) is a fundamental NP-hard problem.
- NPP can be mapped to a spin-glass problem, allowing for physics-based approaches.
- Understanding the solution landscape is crucial for tackling NP-hard problems.
Purpose of the Study:
- To apply the multicanonical method from statistical physics to the NPP.
- To investigate the spectral degeneracy of NPP and its variations.
- To analyze the impact of generalizing NPP to Q partitions on solution complexity.
Main Methods:
- Utilizing the multicanonical simulation method.
- Computing spectral degeneracy to quantify solution counts for specific costs and cardinality differences.
- Examining an extension of NPP for Q partitions (Q>2).
Main Results:
- The spectral degeneracy was computed for the NPP, providing insights into solution distribution.
- A fundamental difference in spectral degeneracy was identified for the generalized NPP with Q>2 partitions.
- This difference in degeneracy offers a potential explanation for the computational difficulty of generalized NPP.
Conclusions:
- The multicanonical method is a viable approach for studying the NPP.
- Generalized number partitioning problems (Q>2) exhibit distinct spectral degeneracy characteristics.
- The observed differences in spectral degeneracy may underlie the inherent difficulty in finding optimal solutions for generalized NPPs.