# Tag Info

## Hot answers tagged subset-sum

6

Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum. To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction. (Implicitly, we get a reduction from FACT to SAT by Cook's ...

5

You are on the right track. It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.) Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths. Let the ...

4

If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$) If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct). If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order ...

3

There are many functions that satisfy your condition. Here are a few. $a_i=1+c^{-i}$, for some constant $c\ge 2$. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer between 1 and $p_i-1$. $a_i =1+\alpha^i/\lceil\alpha^i\rceil$, for any positive transdental number $\alpha$. For example, you can take $\alpha = \pi$ or $\alpha=... 3 This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset$S$from a set with a certain sum$n$. Suppose we are given such an instance and that your problem can be efficiently solved. Then we can transform the instance by making$S' = S \cup \{x, x - n\}$for some sufficiently large$x$and solving your ... 3 All weakly NP-complete problems are NP-complete by definition, so yes, a polynomial time algorithm would imply P = NP. 3 This is NP-hard. The associated decision problem is NP-complete. There are various ways to prove that. For instance, there's a straightforward reduction from exact cover; let the target array be all-ones, and then you have an instance of the exact cover problem, which is NP-hard. Your problem is an instance of multi-dimensional subset sum (or multi-... 3 The problem can be solved in polynomial time. If any of the$a_i$are zero, then the answer is "yes" (you can set the corresponding$x_i$to 1, and all other$x_j$to 0). So let's assume all of the$a_i$are non-zero. If all of the$a_i$are strictly positive, then the answer is "no" (if$x_i$is the one that's set to something non-zero, then$x_i>0$... 3 I'm assuming by$sum(i)$you mean that given an ordering of the$k$partitioned subsets, sum over all elements of the$i$th subset. The$k=2$case is the optimization variant of the set partitioning problem (https://en.wikipedia.org/wiki/Partition_problem) which is known to be as hard as subset sum. EDIT: The general case is as difficult by reduction from$...

3

Suppose that you could solve this in $T(n)$. Given a list of positive integers $a_1,\ldots,a_n$ and a target $T$, consider the two instances $a_1,\ldots,a_n,-T$ and $a_1,\ldots,a_n,-T+1$. Denoting by $N(\cdots)$ the number of positive sums, we get: $N(a_1,\ldots,a_n,-T)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is larger than $T$. $N(a_1,\... 3 It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset$N'$is at least$B$(which implies that it must actually be exactly$B$) if and only if the corresponding subset sum instance has answer "yes". 3 The observation is that the denominator of the reduced fraction$1/p_{i_1} + \cdots + 1/p_{i_m}$is$p_{i_1} \cdots p_{i_m}$. To see this, it suffices to notice that the (unreduced) numerator isn't divisible by any$p_{i_j}$. Indeed, the numerator is simply $$\frac{p_{i_1} \cdots p_{i_m}}{p_{i_1}} + \cdots + \frac{p_{i_1} \cdots p_{i_m}}{p_{i_m}}.$$ All ... 3 However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from the same positions) evaluates to 0? All other subsets in T should evaluate to 1. No, this is impossible. Consider$S=\{1,2,3\}$and$W=3$. Our set$T$should ... 3 This is not what amortized analysis means: you can not infer the worst case runtime of an algorithm by plotting the actual execution time on larger and larger instances of some specific structure. Sadly, that doesn't prove you have a polynomial-time algorithm. Even when you want to do experimental work, there are other parameters to vary besides the size of ... 3 We give a Turing reduction from the$\mathrm{SubsetSum}$problem. Suppose we are given a$\mathrm{SubsetSum}$instance$(A, k)$where w.l.o.g.$A$only contains positive integers, i.e. we want to find a set$X \subseteq A$such that$\sum_{x \in X} x = k$and define the set$A' = A \cup \{- k\}$. We want to show that$f(A') = 0$if and only if$(A, k) \in \...

2

This problem lies in P. To see this, formulate this problem it as an integer linear program (ILP): For $x\in \mathbb{Z}^n$, maximize $\sum_{i=1}^n x_i$ under the constraint $\sum_{i=1}^n a_ix_i = 0$ and $x_i\geq 0$ for all $i\in \{1,\ldots,n\}$. Let's have a look at the relaxed version of this ILP: For $x\in \mathbb{R}^n$, maximize $\sum_{i=1}^n x_i$ ...

2

This answer assumes that a Yes instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$ is one in which there is a subset summing to either $X$ or $X+1$. Given an instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$, construct an instance of subset sum with elements $x_0,\ldots,x_{n-1},1$ and target $X+1$...

2

Nice question! Given a range of integers $\{a,a+1,...,b−1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Well, this problem can be solved in $O(n)$ time, where $n$ is the number of given integers. (Continuity of $k$-sums). Given integers $\{a,a+1,...,a+n-1\}$, an integer $k$, $1\le k\le n$ and an integer $s$, there are $k$ integers ...

2

Let us define a predicate $$T(i,k_1,...,k_n)\in\{True, False\}$$ Where $T(i,k_1,...,k_n)$ means "using the $i$ first values of $S$, we can find $n$ disjoint subsets with sums $k_1, ... k_n$". The answer you are looking for is $T(|S|,K,..,K)$ where $K$ appears $n$ times. We have the following recurrence formula : $$T(i,k_1,...,k_n) = \left\{ \begin{matrix} ... 2 This problem is strongly NP-hard because it generalizes the 3-Partition problem. That means that it has no efficient (polynomial-time) algorithm, unless P=NP. 2 Hint: suppose that we are able to solve your problem efficiently. Then what if we take an arbitrary subset sum problem and multiply all elements by 2, as well as the target? 2 It's not clear how to formally define worst-case (or near-worst-case) instances, but here is something you could try. The idea is to combine the following two tidbits: We know some hard instances for 3SAT. There is a reduction from 3SAT to SUBSET-SUM. The hard instances for 3SAT are random instances at the correct clause density, which is just below the ... 2 Suppose that the value at location i is j. According to the continuity of k-sums (mentioned in an answer to the linked question), the range of possible sums of values at locations 1,\ldots,i-1 is$$(i-1)a + \binom{i-1}{2},\ldots,(i-1)(j-1) - \binom{i-1}{2}.$$Similarly, the range of possible sums of values at locations i+1,\ldots,k is$$ (k-i)(j+1) ...

2

This problem is $\textrm{NP}$-hard by a reduction from (the decision version of) set-cover: given an integer $k$, a set of items $I = \{x_1, \dots, x_n\}$ and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^I$ of subsets of $I$, decide whether there is a subset $C$ of $S$ such that $|C| \le k$ and $\bigcup_{S_j \in C} S_j = I$. Given an instance of set-...

2

I will assume that initially $y=0$, as this makes no difference in your problem. Look at the very last two elements $a,b$ that you will apply your operation on: The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b],$y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$. Notice that $a$ (resp. ...

2

For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can ...

2

Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$. In the other direction, the idea is to add to the collection a small set of items satisfying the following two ...

2

Showing that this your problem is in NP is easy. To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.

2

Assuming you are looking for $S' \subset S$ with minimal $\sum_{x \in S'} x > X$ like Steven suggested, then you should be able to reduce the problem to an instance of knapsack with weights $w_i$ and costs $c_i$ with $w_i = c_i = s_i$ for every $s_i \in S$ where the weight of the knapsack is bounded by $X$. If the solution $K := \sum_{x \in S'} x$ is not ...

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