Skip to main content
Share Your Experience: Take the 2024 Developer Survey
16 votes
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 ...
Ryan Williams's user avatar
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
  • 903
5 votes
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$ ...
Jeffrey Shallit's user avatar
5 votes

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 ...
David Eppstein's user avatar
4 votes

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 ...
D.W.'s user avatar
  • 12.1k
3 votes

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$ ...
Marzio De Biasi's user avatar
3 votes
Accepted

Is partitioning a multiset into two multisets with equal averages NP-complete?

One NP-hard variant of the PARTITION problem is as follows: INSTANCE: $2k$ positive integers $a_1,\ldots,a_{2k}$ with $\sum_{i=1}^{2k}a_i=2A$ QUESTION: Does there exist an index set $I\subseteq\{...
Gamow's user avatar
  • 5,772
2 votes

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 ...
Andrew Morgan's user avatar
2 votes
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 ...
D.W.'s user avatar
  • 12.1k
2 votes

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 ...
Sasho Nikolov's user avatar
1 vote

strong NP-completeness of multi-dimensional Equal-Subset-Sum

EDIT: I did not answer the original question about EQUAL SUBSET SUM but instead described a reduction for the PARTITION version. I am leaving it here since the OP found this answer useful. It may be ...
Chandra Chekuri's user avatar
1 vote
Accepted

Feature selection problem under promise

Yes. The problem of feature selection under constraints is relevant and was studied very well in multiple scenarios. You may want to look at these papers for reference. Beyond distributive fairness ...
Vidyadhar Rao's user avatar
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 ...
D.W.'s user avatar
  • 12.1k
1 vote

Strongly NP-complete variants of subset sum or partition problem

I found a strongly NP-complete variant of partition (which does not take advantage of special number representations ). It is known as Product Partition problem (similar to partition problem but with ...
Mohammad Al-Turkistany's user avatar
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$...
nikhil_vyas's user avatar

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