New answers tagged

9 votes
Accepted

How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

The problem itself was studied in this paper and was proved to be $\mathsf{NP}$-complete given the target set $T$ as the input. For this specific instance $T=\{1,1/2,1/3,\ldots,1/n\}$, we can show ...
Wei Zhan's user avatar
  • 828

Top 50 recent answers are included