おそらくご存じのとおり、このSUBSET-SUM問題は、一連の整数のサブセットの合計が指定された整数になるかどうかを判断するものとして定義されています。(整数のグループの合計がゼロになるサブセット合計の別の定義がありますが、ここではこの定義を使用しましょう)
たとえば、合計すると((1,2,4,5),6)です。私たちはそれがtrue(2,4)6(2,4)"solution"
さらに、引数の合計((1,5,10),7)がfalse7
私の質問は、引数の数のセットが与えられた場合SUBSET-SUM、可能な解の数に多項式の上限があるかどうかです。最初の例では(2,4)とがあり(1,5)ました。
SUBSET-SUMNP完全であるため、ポリノメール時間で決定することはおそらく不可能であることがわかっています。ただし、私の質問は決定時間とは関係ありません。ソリューションのリストのサイズについて厳密に質問しています。
明らかに、引数の数の累乗セットのサイズが解リストのサイズの上限になる可能性がありますが、これは指数関数的に増加します。私の直感では、多項式の境界があるはずですが、これを証明することはできません。
これは宿題の質問のように聞こえるかもしれませんが、そうではないことを信じてください。私は CS 理論の特定の側面を独学しようとしていますが、これが私の考えが私を導いたところです。