部分和問題

ウィキペディア

部分和問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 06:02 UTC 版)

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