数分割問題 — 知識ノート

与えられた数の集合を 2 組に分け、和の差を最小にする問題。 Number Partitioning。

\min_{s \in {- 1, + 1}^{n}} | \sum_{i = 1}^{n} s_{i} a_{i} |

$s_{i} = + 1$ なら集合 A、 $- 1$ なら集合 B に入れる。

見た目に反して難しい#

問題の記述は 1 行で済むのに NP 困難。 Garey と Johnson が「最も簡単な難しい問題」と呼んだことで知られる。

一方で、数の桁数が小さければ動的計画法で擬多項式時間で解ける（弱 NP 困難）。「入力の値の大きさ」が計算量に効く点が特徴的。

相転移#

数を ${1, \dots, 2^{m}}$ から引くとき、 $m / n$ を変えると 完全分割（差が 0 または 1）が存在する確率が急激に変わる。 $m / n \approx 1$ を境に、ほぼ存在する側からほぼ存在しない側へ移る。統計物理と組合せ最適化を繋ぐ題材としてよく取り上げられる。

QUBO / イジング表現#

上の式の絶対値を二乗すれば、そのままイジング模型のエネルギーになる。

H = {(\sum_{i} s_{i} a_{i})}^{2} = \sum_{i, j} a_{i} a_{j} s_{i} s_{j}

すべての組 $(i, j)$ が結合するので完全結合。量子アニーリングのハードウェアで扱うときは、この密な結合が制約になる。

参考文献#

Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. https://dl.acm.org/doi/10.5555/578533
Stephan Mertens. Phase Transition in the Number Partitioning Problem. Physical Review Letters 81(20), 1998. https://doi.org/10.1103/PhysRevLett.81.4281
Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics 2, 2014. https://doi.org/10.3389/fphy.2014.00005