力まかせ探索
力まかせ探索の主な欠点は、多くの実際の問題では解候補数が極めて多数になってしまうという点である。
例えば、上述のようにある数値の約数を求める場合、解候補数は指定された数値 n によって決まる。従って n が十進で16桁なら、探索には少なくとも 10 個の機械語命令を費やすことになり、これは一般的なPCでは数日に及ぶ。n が無作為な64ビットの自然数なら、十進では平均で19桁となり、探索には約10年かかる。
この解候補数の急激な増大は、どんな問題でも発生しうる。例えば、10文字の並べ替えをして特定の並びを見つける場合、10! = 3,628,800個の解候補があることになるが、この程度ならばPCで1秒以内に生成してチェックできる。しかし、たった1文字追加して問題のデータサイズが10%増加しただけで、解候補数は1000%の増大になる。20文字になると解候補数は 20! すなわち約 2.4×10 であり、これを探索するには約1万年かかる。この好ましくない現象を一般に組合せ爆発と呼ぶ。