組合せ爆発
コンピュータネットワークにおいて、ノードを追加していくと必要な通信路が急激に増大する。このことを組合せ爆発と称する。ただし、実際には指数関数的に増えるわけではなく、厳密にはせいぜい多項式的増大である。
2つのノード間で通信する必要があるとき、1対1の適当な通信路1本で直接接続すればよい。しかし、3つめのノードを追加すると、通信路が3本必要となる。4ノードでは6本、5ノードでは10本、6ノードでは15本と増えていく。これを一般化すると、n ノードでの通信路数l は次のように、n の2乗のオーダーで増加する。
l = n ( n − 1 ) 2 {\displaystyle l={\frac {n(n-1)}{2}}}
これを減らすためのひとつの方法は、情報を媒介する汎用的手段を中心に置くことであり、この場合通信路の数はノード数n に等しくて済む。しかしこの場合の欠点は、
1対1では電話やテレタイプのように特に手順らしい手順を定めなくとも通信できるかもしれないが、媒介手段に対応するためには通信内容に付加された宛先に基づく経路制御をする必要があるのでTCP/IP、SMTPなど何らかの通信プロトコルを導入する必要が生じる点
中心の媒介手段が障害や性能不足に陥れば全部の通信が影響を受ける点
である。2. の欠点のために、実際の設計では必ずしも通信路の数を減らしさえすればいいわけではなく、ある程度の冗長性を残した複雑なシステムを構築することが多い。
組合せ爆発(くみあわせばくはつ、英: combinatorial explosion)は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ(combination)的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。