指数的爆発

提供: ORWiki
2007年9月3日 (月) 17:16時点におけるSakasegawa (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【しすうてきばくはつ (exponential explosion)】

組合せ最適化問題の解集合が, 問題のサイズが大きくなるにつれて爆発的に膨らむことをいう. 組み合せ的爆発ともいう. すなわち, を問題のサイズとするとき, , などのように指数的あるいは組合せ的に増大する. この性質は, 多くの組合せ最適化問題にとって, 効率のよい解法を開発する上で根源的かつ致命的な障壁となることがある. NP困難性に代表されるように, それを理論的に打破する解法開発の可能性が絶望的であることが示されている問題も多い.