Consider the following special case of SUBSET SUM

Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary.

Encoding: These inputs (compactly) encode a list $L$ of length $2^k$ where there are exactly $\binom{k}{i}$ terms of the form $a^{k-i}b^{i}$, for $i=0, \dots, k$.

Output: Is there a subset $D$ of $L$ whose sum is precisely $t$?

A certificate for this problem is a list $(n_0, \dots, n_k)$, where $n_i$ is the number of terms of the form $a^{k-i}b^{i}$ that exist in $D$. Assuming that $k$ is given in unary, such a certificate can be verified in polynomial time.

Any thoughts on whether this problem might be NP-Hard?

The setup is quite strange since even though the problem is closely related to subset sum, the inputs $a,b,k$ encode a list $L$ that is long, so it is not entirely clear how or if a connection exists.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.