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 ...
- 27.3k
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$ ...
- 6,967
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 ...
- 50.9k
5
votes
Accepted
On Zero sum perfect matching
The problem is in RP in both (A) and (B) by a variation of Lovasz's algorithm:
Fix a finite field $F$ of characteristic $2$ on at least $q=4m\max_i |a_i|$ elements.
Consider the graph's Tutte matrix $...
- 3,254
5
votes
Accepted
NP completeness of linear $0-1$ assignment problem
If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:
Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset ...
- 22.6k
4
votes
NP completeness of linear $0-1$ assignment problem
It seems that we can reduce Subset Sum to your problem (2). Hence, your problem (2) is NP-complete.
Consider the following formulation of Subset Sum.
Instance: A multi-set consisting of $n$ ...
- 5,127
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\{...
- 5,772
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$ ...
- 22.6k
3
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 ...
- 11.7k
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 ...
- 18.1k
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 ...
- 1,429
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 ...
- 11.7k
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 ...
- 11.7k
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$...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible