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 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.
This has been studied, see http://www.mathnet.or.kr/mathnet/kms_tex/978590.pdf and the somewhat more interesting: NEWMAN POLYNOMIALS WITH PRESCRIBED VANISHING AND INTEGER SETS WITH DISTINCT SUBSET SUMS PETER BORWEIN AND MICHAEL J. MOSSINGHOFF (available online) See also the references in: http://garden.irmacs.sfu.ca/?q=op/sets_with_distinct_subset_sums None of these answers your question, but I think this is the state of the art... 


In the modern language, sets with all subset sums pairwise distinct are often called dissociated. Maximal dissociated subsets of a given set are important in Additive Combinatorics and Fourier analysis, although I cannot recall anybody ever addressing the algorithmic aspect. Yet another reference you may find useful: http://math.haifa.ac.il/~seva/Papers/DisBases.pdf. Added: taking into account the interpretation of a maximal dissociated subset of a given set $A$ as a "basis of $A$ over the set $\{1,0,1\}$", it may be reasonable to try and adjust one of the standard algorithms of finding a maximal independent subset of a given set in a vector space. 

