Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a subset $S=\{x_1, x_2, x_3, ... x_m\}$ with $m$ elements in it. Each of these elements is between $1$ and $m^2$. Given an instance of this problem and a sum, $y$, I want to place an upper bound on the number of subsets of $S$ that can sum up to $y$. Any crude polynomial upper bound would work for me. (I need this upper bound for some proof I am constructing for a cryptography problem).

share|improve this question
    
Seen this? –  J. M. May 8 '11 at 13:11
1  
@J.M. This variation of subset sum is not NP complete. –  AnkurVijay May 8 '11 at 13:13
1  
Just checking. :) –  J. M. May 8 '11 at 13:17
    
@Shreevatsa no i was hoping for a polynomial lower bound, but as yuval has explained, there's no such bound in general. –  AnkurVijay May 10 '11 at 2:55
    
I mean polynomial upper bound for a general instance –  AnkurVijay May 10 '11 at 3:09
add comment

1 Answer 1

up vote 4 down vote accepted

If all elements are equal to $1$ and $y = m/2$ then the number of subsets is $$\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right).$$

Here's an example with all elements different. Let $S = \{1,\ldots,m\}$ and $y = (m+1)m/4$. The number of subsets is at least $$\binom{m/2}{m/4} = \Theta\left(\frac{2^{m/2}}{\sqrt{m}}\right).$$

share|improve this answer
    
Right, thanks. Also now i see that since the size of the domain is $2^m$ and the size of the range is $m^3$ (the elements can only sum up to at most $m^3$) the average number of preimages is also exponential. –  AnkurVijay May 10 '11 at 2:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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