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