# 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 ...
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$ ...

### 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 ...
Accepted

### Strongly NP-complete variants of subset sum or partition problem

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$ ...

### 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 ...

### A dominate vector subset sum problem

It's hard for $k\ge 2$ by a reduction from Partition. Let's first look at $k = 3$. Suppose that the input to Partition is the numbers $x_1, \ldots, x_n$, and their sum is $S$. For each $i$ create a ...

### Subset product problem

Let $S_0=\{1\}$. For $i = 1,...,n$, set $S_i\gets \{xy\mod b : x\in S_{i-1},y\in L_i\}$. Then just check whether $a \in S_n$. It's obviously correct, since $S_i$ contains the residues which can be ...
Accepted

### Complexity of $r$-sum as a function of integer sizes

There is a straightforward dynamic programming algorithm with complexity $n \times 2^{O(r \cdot n^{1/k})}$. This is pretty slow. For $r=2$, you can use algorithms for the birthday paradox to find a ...
1 vote
Accepted

### reducing this problem to a decision problem

Your problem is coNP-hard, by reduction from SAT. In particular, using inequalities $x \ge 1$, $x \le 0$ and interpreting $0$ as false and $1$ as true, we can encode any SAT formula $\varphi$ into ...
1 vote

### Subset product problem

The meet in the middle approaches that work in subset sum and k-sum should also work here with slight modifications. It can be solved in $\tilde{O}\left(n^{m/2}\right)$ by constructing two lists $L_1$...

Only top scored, non community-wiki answers of a minimum length are eligible