Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

### An obstruction like ETH

ETH itself precludes this possibility. In https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf we show that any $n^{O(1)} n^{k/\alpha(k)}$ time algorithm for k-SUM, for any monotone nondecreasing ...
• 27.5k
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 ...
• 903
Accepted

### Subset Sum Problem and hard looking instances that are not really hard

In my opinion, this is an utter triviality, so unimportant that no one would remark on it. Furthermore, the chance that $t$ numbers chosen at random would have gcd > 1 is vanishingly small once $t$ ...
• 6,986

### Variant of Subset Sum Problem with Changing Bound

It's still NP-complete, via a reduction from the partition problem (in the form of: given a collection of $n$ positive numbers $x_i$, where $n$ is even, partition the numbers into two subsets with ...

### Interesting real life problem similar to subsetsum /bin packing problem

Your problem is at least as hard as bin-packing. In particular, optimizing objective (a) basically is the bin-packing problem (in particular, bin packing is the special case where all drums have ...
• 12.1k
It's like cheating, but if you change the representation of the numbers in the input then the problem becomes strongly NPC: SUBSET SUM OF FACTORIZED SEMIPRIMES "SUBSUMS" Input: A list of $N+1$ ...