6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You have not accepted answers provided to any of your questions, and it is not considered nice. Please check FAQ. $\endgroup$ – Tsuyoshi Ito Dec 31 '11 at 3:20
  • 3
    $\begingroup$ 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). 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. $\endgroup$ – Tsuyoshi Ito Dec 31 '11 at 20:18
  • $\begingroup$ What does it mean to have $n$ integers bounded by a polynomial in $n$? $\endgroup$ – Tyson Williams Jan 2 '12 at 14:10

Your Answer

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

Browse other questions tagged or ask your own question.