17

The problem is known to be NP-complete: On the equal-subset-sum problem, Woeginger and Yu, IPL'92.


16

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 unbounded function $\alpha$, would imply ETH is false.


15

Here is a reduction from PARTITION to this problem. Let $(a_1,\dots, a_n)$ be an instance of PARTITION. Assume that $a_1\leq a_2\leq \dots \leq a_n$. Let $N$ be a “very large number”, e.g. $N = (\sum_{i=1}^n |a_i|) + 1$. Consider the instance $$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$$ ...


14

It seems to me the pseudo-polynomial time dynamic programming algorithm for Subset Sum problem also works for this problem. For each vertex $v_i$, we compute the set $L_i$ consisting of all possible values of paths ended at $v_i$. Then, we have the recurrence relation: $L_i=\{g(v_i)\}\cup\{x+g(v_i)\mid x\in \bigcup_{j\in prec(i)} L_j\}$. Following a ...


12

Here are some references, not a self-contained answer to the question. For self-contained answers, see other people’s answers and comments. Assuming that symbol ℕ in the question denotes the set of nonnegative integers, your problem is called the feasibility version of the change-making problem. Chapter 5 of Martello and Toth [MT90] states that it is NP-...


11

Kellerer et al. (1997) gives with accuracy $\epsilon$ a $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$ time and $O(n + 1/ \epsilon)$ space approximation scheme. Further improving on this, Kellerer et al. (2003) gives a FPTAS with $O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$ time and $O(n+1/ \epsilon)$ space. ...


8

Firstly, using exponentiation to go from SS to SP works (using base 2 rather than base $e$), but blows up the size of the numbers involved. Weak NP-hardness means that if the numbers are small (or more precisely, denoted in unary), the problem is no longer hard. Hence, using exponentiation creates exponentially sized instances of SP even for the easy ...


7

As said by RB in the comment, if $X_1 \cup X_2 = X; X_1 \cap X_2 = \emptyset$, then setting $B=0$ makes your problem equivalent to PARTITION. But even with the relaxed conditions: $X_1,X_2 \neq \emptyset, X_1, X_2 \subseteq X; X_1 \cap X_2 = \emptyset$ (i.e. $X_1,X_2$ not necessarily form a partition of $X$) the problem is still NPC: set $B = 0$ and it ...


6

I think that SUBSET SUM reduces to this problem. Take an instance of subset sum, $a_i$, $b$, and for simplicity suppose every number has $n$ digits (possibly starting with zeros). Now we will make all the numbers much longer. We modify $b$ so that it starts with "n"00001000010000100001... where "n" is the base two representation of n, then it is followed by ...


5

Here is some information on random instances of subset sum. This should give you a starting point at least. The main factor influencing the computational difficulty of solving (random instances of) subset sum is the relationship between the number of available terms, $n$, and the terms' size, $M$. (This is different than the 'possible combinations' idea you ...


5

Regarding the problem of equivalence of Subset Sum and Subset Product There is an technicality regarding Subset Product. Product of x's = T is actually Psuedopolynomial if T is not exponential! So the proofs of Subset Product being NP Hard are not (for technical reasons!!!) quite correct! However given a promise that T is Large Then the reduction via ...


5

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$ is large. (There is an explicit formula, which says that t integers chosen at random from the interval [1..n] will have gcd 1 with probability tending to $1/\...


5

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 equal sums). This exact form of the partition problem is not one of the ones mentioned by Garey and Johnson (SP12); in particular they don't mention the constraint ...


5

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 $T(r)$ where you replace indeterminate $x_{ij}$ by $y_{ij}r^{a_{ij}+q/4}$, where $y_{ij}=y_{ji}$ is a uniformly and independently randomly chosen element in $F$ ...


5

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 of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$ You simply pick $n = (m+1)$ and build your set in this way: add $ a_1, a_2, , ..., a_m$ add $m$ zeros ...


4

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$ integers. Question: Does there exist a subset of size at least $1$ that sums to zero? Now, we reduce Subset Sum to your problem (2). Let a multi-set $X$ consisting ...


3

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\{1,\ldots,2k\}$ with $|I|=k$ so that $\sum_{i\in I}a_i=A$? Take the integers $a_1,\ldots,a_{2k}$ together with two copies of the integer $100kA$. It is ...


3

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$ integers: $q_0$ and $A = \{q_1, ..., q_N\}$ each one represented as a (sub)sum of factorized (semiprime) integers; i.e. $q_i$ is given as $p_{i,1} 2^{a_{i,1}} + ... +...


3

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 equal length, so your problem is at least as hard as bin packing), which is known to be NP-complete. Consequently, your problem is NP-hard, too. All the usual ...


3

The problem is indeed NP-complete - reduce from the 3-partition problem where you are given $3n$ positive integers and asked to group them into $n$ groups such that for all the groups the sum of the elements is the same. Note (1) that partition is strongly NP-complete - i.e remains NP-complete when the input numbers are polynomial in $n$. Note (2) that if ...


3

For what regards point 3: the problem remains NP-complete: if $m$ is a parameter, then it is simply a generalization of SUBSET SUM; if $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $p = 2^k$ s.t. $2^k>m(m+1)/2$ and set $m$ target integers in this way: $G = \{ b_1=B,b_2=a_1+1,b_3=a_1+2,...,...


3

Just another (perhaps simpler) reduction from Exact Cover by Three Sets (X3C). Given a set of $3q$ elements $X = \{ x_1,...,x_{3q}\}$ and a collection of 3 elements subsets $C = \{ C_1,...,C_m \}$, does $C$ contain an exact cover for $X$, i.e. a subcollection $C′\subseteq C$, $|C'| = q$, such that every element of $X$ occurs in exactly one member of $C′$? ...


3

It is still NP-complete. Here is a very sketchy reduction from subset sum. The goal of the whole reduction will be to make $T$ unimportant. If the inputs for subset sum are $a_i$, then add $a_i$ and $2^Na_i$ to our inputs, where $N$ is large, but still $poly(n)$. Set $S$ to be $2^N$ times the original subset sum plus $2^N-1$. Set $T$ to be the product of the ...


2

This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that E2CSS is NP-complete: Given integers $A = a_1,a_2,...,a_n\;; a_i > 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) ...


2

I've never heard of this problem before, but it's clearly NP-hard. There's a simple polynomial time reduction from subset-sum to this problem. All you have to do is take an instance of subset-sum such as: {x1, x2, x3, ... , x_n} ...and map it to this instance of the problem you describe: S1 = {x1, x2, x3, ..., x_n}; S2 = {0}. (I initially misread your ...


2

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 expressed as a product of elements, one each from $L_1,\ldots,L_i$. Just using the definition of $S_i$ to compute it, you get a running time of $O(m n b)$, which ...


2

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 solution in time $O(n)$, if a solution exists. A solution will exist with high probability. In fact, for $r=2$, with high probability a solution will exist ...


1

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 vector $v_i$ whose first coordinate is $x_i$, second coordinate is $-x_i$, and the third coordinate is $0$. Add another vector $v_{n+1}$ with first coordinate $0$,...


1

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$ and $L_2$ where $L_1$ is all possible products from first $m/2$ lists and $L_2$ is all possible products for last $m/2$ lists. Now we just need to check if ...


1

I don't know. Using dynamic programming, we can solve this problem in pseudo-polynomial time $O(nN)$, where $n$ is the number of integers in the list and $N$ is the sum of all integers in the list, as follows. For $m \leq n$, $|M| \leq N$, and $c \in \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$, let $T(m, M, c)$ tell whether it is possible to partition the first $...


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