<p>We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of these $n$ numbers such that
for any $T_1,T_2\subseteq S$, the sum of numbers in $T_1$ is not equal to that of $T_2$.
We want the size of $S$ is maximized.
Clearly, the problem is in NP and can be solved in $n^{O(\log n)}$ time (Since $|S|\leq O(\log n)$).
Is this problem polynomial time solvable?
Is this problem studied before? Any help is appreciated. </p>

CC BY-SA 3.0
2011-12-31T03:20:06.907Z
You have not accepted answers provided to any of your questions, and it is not considered nice.  Please check [FAQ](http://cstheory.stackexchange.com/faq#howtoask).
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-31T20:18:55.400Z
This problem (more precisely, its suitably defined decision version) belongs to a class called $\beta_2\mathrm{P}$ for the reason you stated (see [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#betap)).  If your problem is proved to be β2P-complete, then it means that it is not solvable in polynomial time unless P=β2P.  (P≠β2P is probably a reasonable thing to assume, although it is certainly a stronger conjecture than P≠NP.)  Unfortunately, I do not know many β2P-complete problems to start with to prove such a completeness.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-02T14:10:47.507Z
What does it mean to have $n$ integers bounded by a polynomial in $n$?
Tyson Williams
<cc.complexity-theory><ds.algorithms><nt.number-theory>
Find the maximum set whose subset sum is unique for every of its subset
jian
# Find the maximum set whose subset sum is unique for every of its subset

(Asked by: username_0 on 2011-12-30)

We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of these $n$ numbers such that
for any $T\_1,T\_2\subseteq S$, the sum of numbers in $T\_1$ is not equal to that of $T\_2$.
We want the size of $S$ is maximized.
Clearly, the problem is in NP and can be solved in $n^{O(\log n)}$ time (Since $|S|\leq O(\log n)$).
Is this problem polynomial time solvable?
Is this problem studied before? Any help is appreciated.

**Tags:** cc.complexity-theory, ds.algorithms, nt.number-theory
> **Comments:**
> **username_1**: You have not accepted answers provided to any of your questions, and it is not considered nice.  Please check [FAQ](http://cstheory.stackexchange.com/faq#howtoask).  
> **username_1**: This problem (more precisely, its suitably defined decision version) belongs to a class called $\beta_2\mathrm{P}$ for the reason you stated (see [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#betap)).  If your problem is proved to be β2P-complete, then it means that it is not solvable in polynomial time unless P=β2P.  (P≠β2P is probably a reasonable thing to assume, although it is certainly a stronger conjecture than P≠NP.)  Unfortunately, I do not know many β2P-complete problems to start with to prove such a completeness.  
> **username_2**: What does it mean to have $n$ integers bounded by a polynomial in $n$?  

---

## 0 answers

