<p>I've met this problem.
I would like to know to which complexity class it belongs.</p>
<h3>Input</h3>
<ul>
<li>a set of positive integers <span class="math-container">$I$</span>,</li>
<li>an integer <span class="math-container">$m$</span>,</li>
<li>an integer <span class="math-container">$n$</span>.</li>
</ul>
<h3>Question</h3>
<p>Is the number of <span class="math-container">$S \subseteq I$</span> such that</p>
<ul>
<li><span class="math-container">$\sum_{s \in S} s \leq m$</span>, and</li>
<li><span class="math-container">$\forall e \in I \setminus S,\ e+\sum_{s \in S} s &gt; m$</span></li>
</ul>
<p>less than or equal to <span class="math-container">$n$</span>?</p>

CC BY-SA 3.0
2013-05-23T18:20:43.040Z
This seems better suited to cs.stackexchange.
Yuval Filmus
CC BY-SA 3.0
2013-05-24T10:55:34.677Z
@Yuval: are you sure?  It seems to be a special kind of counting problem, confined to maximal-weight elements below a threshold.  I don't immediately see a reduction.
András Salamon
CC BY-SA 3.0
2013-05-24T13:35:08.387Z
@AndrásSalamon Last time I was told not to comment on questions before they get migrated, so I didn't stop to think about this one.
Yuval Filmus
CC BY-SA 3.0
2013-05-24T14:43:49.843Z
I can't find any $YES$ certificate. Moreover, a possible $NO$ certificate, a list of subsets,
could be of exponential size. That's why, to me, it doesn't look like this problem is in $NP$ or in $co-NP$.
s_xavier
CC BY-SA 3.0
2013-05-24T15:25:52.693Z
@Yuval, I think what was meant is that when you think a question is *clearly* off-topic then don't post an *answer* to it on cstheory and wait till it is migrated. I don't think that is in conflict with commenting about the appropriateness of a question, e.g. you can reply to Andras by saying that there is an easy answer.
Kaveh
CC BY-SA 3.0
2013-05-24T16:11:56.683Z
Perhaps a simpler notation for the problem is: $\sum_{s \in S} s \leq m < \sum_{s \in S} s + \min\{e\in I \setminus S\}$
Marzio De Biasi
CC BY-SA 3.0
2013-05-24T16:55:15.163Z
At first glance, the problem seems NP-hard: given an instance of subset sum with elements $a_1= 1 \ll a_2,a_3,...,a_k$ (all $a_2, a_3, ...$ even) and an even target value of $t \geq a_2$ (the subset sum remains NP-complete even forcing those conditions), use your problem with $m = t$ and $n=0$. The number of subsets of $I$ that satisfy the condition $\sum_{s \in S} s \leq m < \sum_{s \in S} s + 1$ is not zero if and only if the original subset sum problem has a solution.
Marzio De Biasi
CC BY-SA 3.0
2013-05-25T05:41:43.647Z
The question is obviously in $PSPACE$. I guess you are asking whether it can be put some below $PSPACE$.
Igor Shinkar
CC BY-SA 3.0
2013-05-25T10:03:07.727Z
Another note: the counting version of subset sum is $\#P$-complete, so (*at first glance* :-) I think that using the reduction sketched above you can prove that your problem is $\#P$-complete, too (one can use binary search to find the exact value of the number of $S \cup \{1\} \subseteq I$ that satisfies the condition)
Marzio De Biasi
CC BY-SA 3.0
2013-05-26T10:21:35.767Z
I don't think that the problem is in PSPACE because the number of subsets is exponential.
s_xavier
CC BY-SA 3.0
2013-05-26T14:22:51.510Z
@s_xavier: it is trivially in PSPACE: you just need to scan the 2^|S| combinations: for (i = 0; i < 2^|S|; i++) check if the corresponding combination (using the 1 bits of i) satisfies the condition, if yes increment the total counter. The loop and the counter take $O(log(2^{|S|}))=O(|S|)$ space, and the sum requires $O(\log \max(s_i) + |S|)$ space.
Marzio De Biasi
CC BY-SA 3.0
2013-05-26T17:23:46.040Z
Ok I understand your argument. I was thinkîng àbout writting the solution
s_xavier
CC BY-SA 3.0
2013-05-27T08:40:10.863Z
It is in PSPACE. I would like a more precise classification.
s_xavier
CC BY-SA 3.0
2013-05-27T09:11:45.543Z
@s_xavier: #P-complete isn't enough?
Marzio De Biasi
CC BY-SA 3.0
2013-05-27T12:38:21.853Z
sharp P complete is nice ... Do you think it is the most accurate possible classification ?
s_xavier
<cc.complexity-theory><ds.algorithms><complexity-classes>
The number of maximal subsets with sum less than $m$
s_xavier
# The number of maximal subsets with sum less than $m$

(Asked by: username_0 on 2013-05-23)

I've met this problem.
I would like to know to which complexity class it belongs.

### Input

* a set of positive integers $I$,
* an integer $m$,
* an integer $n$.

### Question

Is the number of $S \subseteq I$ such that

* $\sum\_{s \in S} s \leq m$, and
* $\forall e \in I \setminus S,\ e+\sum\_{s \in S} s > m$

less than or equal to $n$?

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes
> **Comments:**
> **username_1**: This seems better suited to cs.stackexchange.  
> **username_2**: @Yuval: are you sure?  It seems to be a special kind of counting problem, confined to maximal-weight elements below a threshold.  I don't immediately see a reduction.  
> **username_1**: @AndrásSalamon Last time I was told not to comment on questions before they get migrated, so I didn't stop to think about this one.  
> **username_0**: I can't find any $YES$ certificate. Moreover, a possible $NO$ certificate, a list of subsets, could be of exponential size. That's why, to me, it doesn't look like this problem is in $NP$ or in $co-NP$.  
> **username_3**: @Yuval, I think what was meant is that when you think a question is *clearly* off-topic then don't post an *answer* to it on cstheory and wait till it is migrated. I don't think that is in conflict with commenting about the appropriateness of a question, e.g. you can reply to Andras by saying that there is an easy answer.  
> **username_4**: Perhaps a simpler notation for the problem is: $\sum_{s \in S} s \leq m < \sum_{s \in S} s + \min\{e\in I \setminus S\}$  
> **username_4**: At first glance, the problem seems NP-hard: given an instance of subset sum with elements $a_1= 1 \ll a_2,a_3,...,a_k$ (all $a_2, a_3, ...$ even) and an even target value of $t \geq a_2$ (the subset sum remains NP-complete even forcing those conditions), use your problem with $m = t$ and $n=0$. The number of subsets of $I$ that satisfy the condition $\sum_{s \in S} s \leq m < \sum_{s \in S} s + 1$ is not zero if and only if the original subset sum problem has a solution.  
> **username_5**: The question is obviously in $PSPACE$. I guess you are asking whether it can be put some below $PSPACE$.  
> **username_4**: Another note: the counting version of subset sum is $\#P$-complete, so (*at first glance* :-) I think that using the reduction sketched above you can prove that your problem is $\#P$-complete, too (one can use binary search to find the exact value of the number of $S \cup \{1\} \subseteq I$ that satisfies the condition)  
> **username_0**: I don't think that the problem is in PSPACE because the number of subsets is exponential.  
> **username_4**: @s_xavier: it is trivially in PSPACE: you just need to scan the 2^|S| combinations: for (i = 0; i < 2^|S|; i++) check if the corresponding combination (using the 1 bits of i) satisfies the condition, if yes increment the total counter. The loop and the counter take $O(log(2^{|S|}))=O(|S|)$ space, and the sum requires $O(\log \max(s_i) + |S|)$ space.  
> **username_0**: Ok I understand your argument. I was thinkîng àbout writting the solution  
> **username_0**: It is in PSPACE. I would like a more precise classification.  
> **username_4**: @s_xavier: #P-complete isn't enough?  
> **username_0**: sharp P complete is nice ... Do you think it is the most accurate possible classification ?  

---

## 0 answers

