組合せ的爆発（読み）くみあわせてきばくはつ（英語表記）combinatorial explosion

ブリタニカ国際大百科事典 小項目事典

組合せ的爆発
くみあわせてきばくはつ
combinatorial explosion

ゲームなどの問題において，次に実行可能なステップが多数存在する場合，目的にいたるまでの可能な場合の数が指数関数的に増大し，現代のいかなるコンピュータもそれを処理しきれないようなことがしばしば生じる。これを組合せ的爆発という。たとえば碁において次に実行可能な手が 2⁷ (128) あったとし，勝負が決るまで 200手必要であったとすると，(2⁷)²⁰⁰＝2¹⁴⁰⁰≒10⁴²⁰ となり，1手を1ナノ秒 (10^-9秒) で実行したとしても 10⁴¹¹ 秒必要となって，現実の時間内に解は得られない。

出典　ブリタニカ国際大百科事典 小項目事典