# Tag Info

Accepted

### Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

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 ...
• 39k

### Is integer factorization reducible to subset sum?

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 ...
• 159k
Accepted

### Find the smallest subarray with sum larger than a threshold

You can solve your problem in linear time using a "sliding window" algorithm. Let $i,j$ be two pointers initialized to $1$, and denote by $\sigma(i,j)$ the sum $a_i + a_{i+1} + \dots + a_{j}$...
• 29.5k
Accepted

• 5,479

### Does a polynomial solution to weakly-NP Complete problem mean P = NP?

All weakly NP-complete problems are NP-complete by definition, so yes, a polynomial time algorithm would imply P = NP.
• 151
Accepted

### How to find sets of polynomially bounded numbers whose subset sums are different?

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 ...
• 39k
Accepted

### What is the complexity class of this variant of Subset sum?

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-...
• 159k

### Maximum Equal Sum K Subsequences

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 ...
• 13.4k
Accepted

### Partition array into k subsets

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 ...

• 277k
Accepted

### How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

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 ...
• 13.2k
Accepted

### Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum

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. ...
• 22.6k

### Minimum absolute value of subset sums of integer values

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 ...
• 1,526
Accepted

### Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

But $g(x,a)$ is linear in $a$ so if you can compute it efficiently for two different values of $a$ then you can compute it efficiently for all $a$?
• 46

### Subset Sum With Interval Target

With negative integers permitted Unlike the SSITP problem restricted to positive integers, when negative integers are permitted the problem is NP-complete. I'll show this by reduction from ordinary ...
• 5,479

### 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

For a set $S = \{s_1,\dotsc,s_n\}$. Construct a polynomial $P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}$. Multiply the polynomial by itself three times, i.e., $P(x) \cdot P(x) \cdot P(x)$. Let this ...
• 6,157
Accepted

### Complexity of a variant of Subset Sum problem

The problem is polynomial-time solvable using a reduction to 0-1 knapsack problem. Take a knapsack of size $W = n+1$. Take $n$ items of size $a_i$ and value $a_i$. The maximum value obtained is $n+1$ ...
• 6,157

### Is this set covering problem NP-Hard?

This problem is NP-Hard. Consider a decision problem of this problem: Whether there exists a partition of S, such that |U'| + |U''| = 2|U|? This problem is equal to the problem of 2-DSC, which has ...
• 69
Accepted

### Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The idea is to set $K/2$ as the target. If there is any given number that is at least $K/2$, just return it. Otherwise, all given numbers are $<K/2$. If the sum of all given numbers is $\le K$, ...
• 39k
Accepted

### Subset ${\tt XOR}$ problem

The problem is in $P$. It can be solved in polynomial time with Gaussian elimination. Build a $n\times n$ boolean matrix $M$, whose $i$th row is the $i$th bit-string in $X$. All arithmetic will be ...
• 159k

### Is subset sum problem with multiplicities NP-complete?

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$...
• 8,248
Accepted

### Subset sum into a consecutive range vs. standard subset sum

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 ...
• 277k
The idea is that two sorted lists of length $n$ can be merged into one sorted list of length $2n$ in time $O(n)$. This is a standard procedure used in the mergesort algorithm. Given a list of integers ...