部分和問題のソースを表示

'''部分和問題'''（ぶぶんわもんだい）は、[[計算複雑性理論]]・[[暗号理論]]における問題で、与えられた ''n'' 個の[[整数]] ''a''<sub>1</sub>,...,''a''<sub>''n''</sub> から部分集合をうまく選んで、その集合内の数の和が与えられた数 ''N'' に等しくなるようにできるかどうかを[[判定問題|判定する問題]]である。[[NP完全]]であることが知られている。

この問題は、'''分割問題''' (Number Partitioning) の一般形でもある。分割問題とは、与えられた ''n'' 個の整数 ''a''<sub>1</sub>,...,''a''<sub>''n''</sub> を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。この問題も、NP完全であることが示されている。

部分和問題は、[[ナップサック問題]]に含まれるため、[[動的計画法]]等の手法で解くことができる。（詳しくは、ナップサック問題の項を参照。）

==問題例==
*問題1: {1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？
**答え: 存在する。{1,7,13}
*問題2: {2,4,6,8,10} の部分和で、和が 19 になるものは存在するか？
**答え: 存在しない。（偶数の和は偶数にしかならないから。）

{{デフォルトソート:ふふんわもんたい}}
[[category:計算複雑性理論]]
[[category:群論]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]