組合せ爆発

組合せ爆発（くみあわせばくはつ、英: combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数（指数関数的成長）や階乗などのオーダーで急激に大きくなってしまうために、現実的な時間で解あるいは最適解を発見することが困難になることをいう。 == 概説 == それ以外の通信ネットワーク、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。