Lower bound of computational complexity of knapsack problems

ビッグピクチャー：「不可能」なパズル

想像してみてください。あなたは、とてつもなく難解で巨大なパズルを持っています。コンピュータサイエンスの世界では、これは**ナップサック問題（Knapsack Problem）**と呼ばれています。それは、重さの制限を超えないように、できるだけ価値の高いアイテムをスーツケースに詰め込むようなものです。何千ものアイテムがあり、あなたは完璧な組み合わせを見つけ出さなければなりません。

数十年の間、コンピュータはこの問題に苦戦してきました。解決にかかる時間はあまりにも速いスピードで増大するため、たとえ最速のスーパーコンピュータであっても、大規模なバージョンのパズルを解くには宇宙の年齢よりも長い時間を要してしまいます。このクラスの問題は、**NP完全（NP-complete）**として知られています。

この論文の著者である張志東（Zhidong Zhang）氏は、このパズルが実際にはどれほど難しいのかという「下限（lower bound）」を見つけたと主張しています。言い換えれば、アルゴリズムがいかに賢くなったとしても、コンピュータが理論上到達できる「最も速い時間」を知りたいと考えているのです。

秘密の材料：スピンとフラストレーション

これを解決するために、著者は単にスーツケースを見るのではなく、全く異なる分野、すなわち物理学、特に磁石や「スピングラス（spin glass）」の研究に目を向けます。

• 比喩： 部屋の中に、手をつないでいる人々（スピン）がいると想像してください。ある人は北を向き、ある人は南を向きたがっています。しかし、ここでの落とし穴は、彼らがランダムに繋がっていることです。Aさんは北を向きたいのに、隣の人は南を向きたがっている。これにより、「フラストレーション（葛藤）」が生じ、全員が同時に満足することはできません。
• つながり： 著者は、スーツケースに荷物を詰めること（ナップサック問題）が、これらフラストレーションを抱えた磁石の最も安定した配置を見つけること（スピングラスモデル）と数学的に同一であることを示しています。もし磁石のパズルを解ければ、スーツケースのパズルも解けるのです。

「3D vs 2D」の衝突

著者の発見の核心は、次元間の衝突にあります。

1. 3Dの現実： 磁石（あるいはスーツケースの中のアイテム）は、3次元空間に存在しています。それらはあらゆる方向に繋がっています。
2. 2Dの道具： 物理学者が答えを計算しようとする際、彼らは「転送行列（transfer matrix）」と呼ばれる数学的ツールを使用しますが、これは本質的に平らな2次元のシートです。

メタファー： くしゃくしゃになった糸の玉（3Dの現実）を、糸を切ることなく、平らな紙（2Dの道具）の上に押し広げて平らにしようとしている場面を想像してください。糸は3次元であるため、平らにしようとすると、糸同士が不可能な方法で交差してしまいます。これらの「交差」が、**非自明なトポロジカル構造（topological structures）**を生み出すのです。

著者は、これらの交差こそが「難しさの源」であると主張しています。問題を簡単に（「P」問題として）「押しつぶす」ことはできません。なぜなら、接続の3次元的な性質が、これらの複雑な絡まりを強制的に存在させるからです。

「絶対最小コア（AMC）」

この論文では、**絶対最小コア（Absolute Minimum Core: AMC）**という概念を導入しています。

• 比喩： ナップサック問題を、巨大な多層ビルのようなものだと考えてください。ビル全体を理解するために、すべてのフロアを見る必要はありません。著者は、本質的な難しさが含まれている特定の「コア（核）」となるセクション――わずか2つの層――が存在すると主張しています。
• 発見： この「コア」は、すべての困難で絡まった特徴を保持している、最も小さなバージョンの問題です。著者は、このコアをこれ以上単純化して「簡単な問題」にすることはできないと証明しています。それは、「難しい」と「易しい」の境界線上に位置しています。

「中間領域（NPI）」

長い間、コンピュータ科学者は、問題には以下のどちらかしかないと考えてきました。

1. 易しい（P）： 素早く解ける。
2. 難しい（NP完全）： あらゆる可能性をチェックする（総当たり攻撃）ことでしか解けない。

著者は、NP中間（NP-Intermediate: NPI）と呼ばれる第3のカテゴリーを提案しています。

• メタファー： 階段を想像してください。底には「易しい」があり、頂上には「難しい」があります。著者は、その中間に「踊り場」があると言っています。「コア」モデルはこの踊り場の端に位置しています。
• 結果： ナップサック問題は、「易しい」の方へ完全に崩壊（簡略化）させることはできません。それはこの中間ゾーンに存在しています。それは多項式時間（P）の問題よりは難しく、しかし最悪のケースである総当たり攻撃よりは容易である可能性があります。

新しい速度制限

論文は、将来これらの問題をどれほどの速さで解けるかという主張で締めくくられています。

• 現状： 現在の最良のアルゴリズムは、$1.3^N$（$N$はアイテム数）のように指数関数的に増大する時間を要します。これは非常に低速です。
• 主張： 著者は、「コア」を理解し、特定の並列コンピューティング戦略（問題の各層を同時に解決する手法）を用いることで、速度を$(1 + \epsilon)^N$のようなレベルに改善できることを示唆しています。
• これが意味すること： 必要な時間は依然として増大しますが、以前よりもずっと緩やかに増大します。それは「不可能」から「劣指数関数的（sub-exponential）」（非常に速いが、一瞬ではない）へと移行します。

主張の要約

• 困難さの起源： 難しさは、問題の3次元的な性質と、それを解くための2次元的なツールの間の衝突から生じ、回避不能な「結び目」や「交差」を作り出します。
• コア： ナップサック問題には、これ以上簡単にはできない最小の「コア」バージョンが存在します。
• 中間ゾーン： 「易しい問題」と「難しい問題」の間に、ナップサック問題が属する「中間領域（NPI）」が存在します。
• 解決策： このコアを標的にし、並列処理を用いることで、理論的には現在の手法よりもはるかに速くこれらの問題を解くアルゴリズムを開発できる可能性があります。ただし、それらは依然として複雑なものとなります。

著者は、これは物理学、生物学、金融、および情報技術に適用されるものですが、あくまでこれらの特定の最適化パズルを解くという文脈においてであると述べています。