子集大小爲'k`的子集合是NPC嗎？

Question

我有一個Subset-Sum problem的變化，其中子集的大小是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}

Answer 1

的問題是NPC。

如果你能找到多項式時間內解決你的問題，那麼你可以有多項式時間的解決方案與上限 時間子集和= K *的（你的問題的時間）

Answer 2

這問題是人大子集和問題。事實上，當k是n的^{1- Ω（1）}，甚至O（k）的
與
的

所有在正^{爲數字的組合的promise有at most one solution}

不疑把它放在coNŤIME（N ^（o（K）））/ 2^{o(k*n*log(n))}無限 - 通常，
因爲this paper's Proof of Theorem 5.1給出減少
適用於這樣的k並保留解決方案的數量。