Article

情報科学:困難な最適化問題における相転移の厳密な位置

Nature 435, 7043 doi: 10.1038/nature03602

多くの最適化問題に対して、全数探索よりも効率が十分高いアルゴリズムは存在しないと広く信じられている。これは、多くの実用的問題で最適解を見いだすことは、現在の、あるいは予測されるどの計算機能力でも不可能なことを意味する。この極端な「困難性」の起源を解明するため、計算機科学、数学、そして物理学の分野では20年もの間、制約充足問題のランダム事例における計算複雑性と相転移との関係が研究されてきた。本論文では、このような相転移の位置を見いだす数学的に厳密な方法を示す。この方法では、制約条件を加えたとき、一対の解の間の距離分布を解析する。この分布が発展するときその臨界挙動を見いだすことにより、多くの問題に対して閾値の場所を正確に決定できる。こうしたものには、2つの最もよく研究されている問題、すなわちランダムk-SAT問題やランダムグラフ色塗り問題も含まれる。我々の結果により、この分野における統計物理学の発見的な予言は本質的に正しいことが証明された。さらに、制約充足問題のランダム事例は、解析したアルゴリズムで得られるどの結果も十分超えた解を持つことが実証された。

目次へ戻る

プライバシーマーク制度