1
$\begingroup$

Is the problem

'Given $m=\big\lceil{n^b}\big\rceil$ with $b\in(0,1)$ integers $a_1,\cdots,a_m$ each with $\lceil\log_2 |a_i|\rceil=\big\lceil n^a\big\rceil$ with $a\in[1,\infty)$ is there a subset that sums to zero?'

$NP$ complete?

The reason I ask is this problem can be solved in $2^{O(n^b)}=2^{o(n)}$ time.

$\endgroup$
1
$\begingroup$

Your problem is not really well-defined, since it's not clear what is the parameter $n$. That said, under any reasonable interpretation, your problem is still NP-complete, as can be shown by padding. Given an instance of subset sum, we can create an instance of your restricted subset sum by adding a lot of zeroes to the set.

Subset sum is solvable in polynomial time if the weights are polynomially bounded. More generally, if there are $m$ integers and each one is bounded in magnitude by $B$, then subset sum can be solved in $O(mB)$. In your case the weights are not polynomially bounded.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.