Statistical mechanics of an NP-complete problem: subset sum

Tomohiro Sasamoto, Taro Toyoizumi, Hidetoshi NishimoriJournal of Physics A Mathematical and General 2001 · DOI · arXiv

Abstract

We study the statistical properties of the Subset Sum problem, a classic NP-complete challenge, using the methods and concepts of statistical mechanics. By treating the problem as a physical system, we derive asymptotic expressions for the number of solutions and identify the phase transition boundary where the problem shifts from computationally easy to hard. These results are applied to the Number Partitioning Problem (NPP) as a special case, resolving previous discrepancies in the physics literature regarding negative entropy. We further discuss the limits of applying statistical mechanics to discrete combinatorial problems.

1. Introduction

In theoretical computer science, NP-complete problems like the Subset Sum problem are defined by their worst-case complexity. However, the "typical-case" difficulty—how hard a random instance is to solve—often tells a different story. This paper, originally published in 2001 by Sasamoto, Toyoizumi, and Nishimori, bridges the gap between computer science and many-body physics. By mapping the Subset Sum problem onto a system of non-interacting spins, the authors provide a framework to count solutions and locate the phase transition between solvability and insolvability.

2. The Subset Sum Problem

The Subset Sum problem asks: Given a set $\mathcal{A}$ of $N$ positive integers $\{a_1, a_2, \dots, a_N\}$, does there exist a subset whose elements sum exactly to a target value $E$?

While the problem is computationally difficult in the general sense, the authors investigate sets where elements are drawn uniformly from a range $\{1, 2, \dots, L\}$. The goal is to determine the number of solutions $W(E)$ for a typical instance and understand how this count changes as the ratio between the number of elements $N$ and their magnitude $L$ varies.

3. Methodology: The Statistical Mechanics Approach

To analyze the problem, the authors treat the choice of including or excluding an integer as a state of a physical particle (a spin).

3.1 Hamiltonian and Partition Function

They define a Hamiltonian (energy function) where each $a_i$ is associated with a variable $n_i \in \{0, 1\}$: $$H = \sum_{i=1}^{N} a_i n_i$$ The number of solutions $W(E)$ is the number of configurations of $\{n_i\}$ such that $H = E$. To find this, the authors employ the canonical ensemble and the partition function $Z(\beta) = \sum e^{-\beta H}$.

3.2 Saddle-Point Approximation

Using the method of steepest descent (saddle-point approximation), the authors convert the discrete counting problem into a complex integral. This allows for the derivation of an asymptotic formula for $W(E)$ in the limit of large $N$. Notably, to explore the full range of possible sums $E$, the authors allow the inverse temperature $\beta$ to take negative values, a necessary mathematical departure from standard physical models where energy is usually bounded from below.

4. Key Insights and Results

4.1 The Counting Formula

The primary result is a robust asymptotic expression for the number of solutions $W(E)$. Numerical simulations confirm that this theoretical prediction is highly accurate for random instances.

4.2 Phase Transitions and the Critical Value $\kappa_c$

The authors identify a "phase transition" controlled by the parameter $\kappa = \frac{\log_2 L}{N}$. This parameter represents the density of the problem:

  • The Easy Region ($\kappa < \kappa_c$): Solutions are exponentially abundant. In this phase, finding a subset that sums to $E$ is statistically likely and computationally straightforward.
  • The Hard Region ($\kappa > \kappa_c$): The number of solutions drops to zero or one. This is the region where the problem becomes computationally grueling, as the "search space" is vast but the "targets" are nearly non-existent.

4.3 Resolving the NPP Paradox

The Number Partitioning Problem (NPP) is a special case of Subset Sum where $E = \frac{1}{2} \sum a_i$. Previous physics literature on NPP encountered a paradox where calculated entropy became negative. Sasamoto et al. demonstrated that this was due to an incorrect assumption of "ensemble equivalence." By correctly applying their statistical framework, they resolved the anomaly and provided a unified description of both problems.

5. Discussion and Limitations

While the statistical mechanics approach provides powerful insights into the "typical" behavior of NP-complete problems, it has limits. The authors acknowledge that their methods are most reliable in the "easy" region. In the "hard" region, the property of self-averaging—where a single random instance represents the average behavior of the whole ensemble—begins to break down. Furthermore, while this analysis helps identify when a problem is likely to be easy, it does not negate the NP-completeness of the problem; specific, non-random instances will always exist that defy typical-case predictions.

6. Conclusion

By treating integers as physical states, Sasamoto, Toyoizumi, and Nishimori successfully applied the tools of the canonical ensemble to a fundamental problem in computer science. Their work not only provides a precise counting formula for Subset Sum solutions but also clarifies the nature of phase transitions in combinatorial optimization, offering a more rigorous foundation for the study of the Number Partitioning Problem.

Summary updated

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.
BibTeX
@article{sasamoto2001statistical,
  author = {Tomohiro Sasamoto and Taro Toyoizumi and Hidetoshi Nishimori},
  title = {{Statistical mechanics of an NP-complete problem: subset sum}},
  journal = {Journal of Physics A Mathematical and General},
  year = {2001},
  doi = {10.1088/0305-4470/34/44/314},
}
Figure