数個の候補から一番よいものを選ぶのは簡単でも、選択肢が増えると急に計算が終わらなくなることがある。候補が一つ増えるたび、組み合わせの数が掛け算で増えていくためである。最適化の難しさは、選択肢の個数だけでは測れない。
選ぶか選ばないかだけでも増える
品物を一つずつ持っていくか決めるなら、各品物には二つの選択がある。10個では2の10乗、つまり1024通りとなる。20個に増やすと約百万通りとなり、品物の数が2倍でも候補数は2倍では済まない。
荷物の重さに上限があり、価値の合計を最大にしたい場合、個々に価値の高い品物を選ぶだけでは最適になるとは限らない。一つの選択が、残りの空き容量と次の選択を変える。条件同士の結び付きが、問題を難しくする。
確かめることと探すこと
候補の荷物の組み合わせを渡されれば、重さと価値を合計して条件を満たすか確かめられる。十分によい組み合わせを一から探す仕事は、それとは異なる。Clay Mathematics InstituteのP対NP問題の解説も、答えの確認と発見の違いを中心に説明している。
ここで、あらゆる最適化が同じように難しいわけではない。問題の構造を使って効率よく解けるものもある。総当たりで候補が多いことだけから、どんな方法でも同じ時間が必要だと結論することはできない。
全候補を調べずに済ませる工夫
探索の途中で、残りをどう選んでも現在の最良案に届かないと分かれば、その枝を調べずに済む。重複する部分問題の答えを保存して再利用する方法もある。条件の構造を見抜くと、単純な総当たりより大幅に計算を減らせる。
実務では、厳密な最適解が必要か、時間内に十分によい解があればよいかも考える。良い候補を見つけることと、それ以上の候補が存在しないと保証することは別の仕事である。「最適な選択」を求める難しさは、候補の増え方と、求める保証の強さの両方から生じるのである。
PやNPは、入力の大きさに対する計算量を扱う理論上の分類である。個々の問題がいつも難しいという意味でも、現在のコンピューターで何秒かかるかを直接示すものでもない。
参考資料
参考資料確認日：2026年10月14日。