# Questions tagged [subset-sum]

Questions about the NP-complete problem Subset Sum.

85 questions
Filter by
Sorted by
Tagged with
28 views

### Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
80 views

### Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows: SSITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$. SSITP Output: ...
40 views

### Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
49 views

### SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
87 views

### Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
23 views

### Prove SubsetSum is polyequivalent to SubsetSum with surplus

I'm solving problem 13.17 of What can be computed?, which is asking to prove $\text{SubsetSum} \equiv_{P} \text{SubsetSumWithFives}$. Here is the definition of SubsetSumWithFives. SUBSETSUMWITHFIVES: ...
34 views

Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$ $$f(\mathbf{x},n) = \sum_{\sigma_1,...,\... 1answer 50 views ### The subset sum problem is not in P because the question is about lossy compressed data? Why not? Where is there a gap or error in my reasoning? The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1). The compression ... 1answer 29 views ### Reduction from SUBSET-SUM to 0-1-INT-PROG The 0-1-INT-PROG problem is given an integer m \times n matrix A and an integer m-vector b, is there an integer n-vector x with A \cdot x \leq b. I am trying to prove that 0-1-INT-PROG ... 1answer 63 views ### Minimum absolute value of subset sums of integer values f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\} How to prove f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}? When \... 2answers 79 views ### Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and ... 0answers 17 views ### Given an abstract argumentation framework, is there a tool that can compute: conflict free, admissible and all extensions? I am trying to find an online/offline tool that can compute the following: Given an abstract argumentation framework <S, R>, where S = {a1, a2, a3, a4, a5} and the attack relation R = {(a1, a2),(... 1answer 562 views ### How to prove that the subset sum problem is polynomially reducible to the knapsack problem I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete. There are two parts to showing knapsack is NP-... 0answers 51 views ### Get n^{\mathrm{th}} element of sorted subset sums I have a sorted multiset (size < 100, real valued) and want to determine the n^{\mathrm{th}} largest of all possible subset sums (including multiplicity in the sums). Attempt at solving : I have ... 0answers 56 views ### Subset selection with maximum sum and minimum variance? So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ... 0answers 16 views ### Showing that Subset Sum Reduces to 3-Partition [duplicate] Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. This is a ... 1answer 75 views ### Reduce Subset-Sum to Sat Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers. SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn }... 1answer 57 views ### Unconstrained subset sum vs constrained subset sum? In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by. Question 1: ... 0answers 32 views ### Is is possible to create a SUBSET-SUM instance that each subset is "unique"? Given a SUBSET-SUM instance S with a weight W, is it possible to create, in polynomial time, a new non-empty instance T (at most the same length as S) with weight M, that for each non-empty ... 1answer 57 views ### How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1? An SUBSET-SUM instance is a list of n integers \{ a_1, a_2,... a_n\}. To evaluate a subset is to output the sum of a subset. However, I want to know, is it possible to create a new instance T, ... 1answer 42 views ### Multi-dimensional Knapsack with Minimum Value constraints for Dimensions In MDK, we have a vector W = \{W_1, W_2, ..., W_d\} where each element corresponds to the maximum weight for the respective dimension in the knapsack. I want to add a conditional constraint: V = {... 1answer 99 views ### Dataset of Hard Instances of SUBSET-SUM I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-... 1answer 50 views ### Converting a Mixed SUBSET-SUM Problem To All-Positive Case Let's say we have a SUBSET-SUM problem with list {x_1,x_2,x_3,...x_N} and weight W, with some of x_i<0. Is there a known way, in polynomial time, to convert this problem into an equivalent ... 2answers 57 views ### Complexity of Subset Sum where the size of the subset is specified I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum. Given a subset S of positive integers and integers k>0 and N>0, is there a ... 3answers 81 views ### Find the smallest group of numbers with sum bigger then X Given a list of numbers S where 0 < s_i < 100, find the minimum sum group of numbers with a sum bigger than X. Each number can be used multiple times. Ex: for S = [3,4.1], X = 10 the ... 1answer 410 views ### How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack? I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of O^*(2^{n/2})? ... 0answers 126 views ### How to trace Subset from Boolean DP table in the Subset Sum Problem I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result. My questions are. How did someone conclude that ... 1answer 76 views ### How to prove the NP-completeness of MOD-PARTITION MOD-PARTITION: Given a set of integers A={a_1,...,a_n}, their weights w = \{w_1, w_2, \dots, w_n\} and the number k, does there exist a subset X of A such that: (\sum_{x \in X} w(x) * x) \... 1answer 92 views ### Enumerate all valid orders of subset sums Given an positive integer n, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of \{1,\ldots,n\}. For example, when n=2, the ... 1answer 333 views ### Two versions of Subset Sum Problem I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound W and a collection of n items, each with a positive integer weight w_i, ... 2answers 470 views ### Subset sum problem for permutations Given permutations g_1,\,\ldots, g_m \in S_n of size n and target permutation g \in S_n, decide if there exists a subset of \{g_1,\, \ldots, g_m\}, which composition in some order (or, ... 0answers 37 views ### Finding a non negative combination of integers that adds up to a certain number [duplicate] I have a set of positive numbers: {n_1,n_2,...n_k} s.t. n_1>n_2>\dots >n_k. I want to find an array of non-negative integers c_1,c_2,\dots,c_k such that$$n_1c_1 + n_2c_2 + \dots + ...
Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...