データの数に対して計算の量が指数関数的に増大するような問題では、データの数が多くなると計算量がふつうには手に負えなくなるほど大きくなってしまう。それを計算量爆発問題と呼ぶ。人間がコンピューターに解かせたい問題の多くは、計算量爆発問題である。巡回セールスマン問題、最大派閥抽出問題、暗号解読問題などが知られ、この解決のために、量子コンピューター、DNAコンピューター、グリッド・コンピューティングなどが注目されている。

図「計算量爆発問題」