1
$\begingroup$

I've been trying to search for a problem which I think could be similar to Subset Sum. The definition of the problem would be as follows:

Given k $\in$ $\mathbb{Z}$ and S = {$s_1$,...,$s_n$} s.t. $s_i \in \mathbb{Z}$, how many subsets $S' \subseteq S$ exist s.t. $\sum S' \geq k$.

I don't know if this problem has been studied previously, but I can't find anything. Could someone help me?

$\endgroup$
1
$\begingroup$

This problem is not in NP because it is not a decision problem. Instead it would lie in #P because you want it to output the number of accepting paths of a non-deterministic machine.

You can look for some #P problems but I don't think each NP problem has a studied equivalent there.

If you changed it into a decision problem of: 'Is there more (or less) than $l$ subsets with $\Sigma_{s\in S'}s \ge k$ then this would be a decision problem but since $l$ is bounded by $2^n$ this is still not in NP. It is surely in PSPACE, but I can't put it anywhere lower in the polynomial hierarchy right now.

$\endgroup$
3
  • $\begingroup$ Since it's $\geq k$ and not $=k$, it might actually be polytime, no? $\endgroup$
    – Pål GD
    Jan 12 at 12:51
  • $\begingroup$ I don't think it's polytime even with that. I just found that there exists a generalization of this problem called Littlewood-Offord problem $\endgroup$
    – Maitgon
    Jan 13 at 10:29
  • $\begingroup$ It's true I didn't realize the inequlity might be actually a much simpler problem. The Littlewood-Offord lemma binds only the solution, not the runtime as far as I can tell. $\endgroup$
    – Ordoshsen
    Jan 13 at 21:07

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.