reduction - サブセットのサイズが k のサブセットの合計は NPC ですか?

Question

サブセットのサイズがあり、すべての整数が正（ゼロではない）であるサブセット合計問題のバリエーションがあります。k

オンラインで見られるように、この問題は疑似多項式時間で動的計画法を使用してかなり解決できます。

NPCこの問題がであるか、P( であると仮定して) であるかを判断する必要がありP!=NPます。

私はサブセットサムの問題から削減しようとしましたが、すべての整数がゼロより大きくなければならないという制約に問題がありました。それ以外の場合は、入力をkゼロの整数で埋めただけです。

問題の正式な定義:

L={<S1,S2,...,Sn,T,k>|There exists a subset I of S1,...,Sn of size m which sums up to T}

score 2 · Accepted Answer

その問題はNPCです。実際、k が n ^{1- Ω (1)}にあるとき、

数値はすべて n ^O(k)
にあり、最大でも 1 つの解
があるという約束があります。

この論文の定理5.1の証明では_ _ ^_ _ はそのような k に対して機能し、解の数を保持します。

score 2 · Accepted Answer

問題はNPCです。

問題の多項式時間解を見つけることができれば、サブセット合計の上限時間 = k * (あなたの問題の時間) を持つサブセット合計問題の多項式時間解を得ることができます。

2 に答える 2