# Complexity class of a subset problem similar to subset sum

What could be the complexity class of the following problem:
Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \subset S : \sum{S'} = K$ such that the elements of $S'$ form an arithmetic series with difference $d$ and $a = x_1$. So $S' = \{x_1, x_2 ..., x_n\}$ $: x_{i+1} = x_i + d$ for $2 \le x_i \le n$.

The problem is in NP, since given a solution set $A$ it is possible to check in polynomial time if $\sum{A} = K$.

The regular [0,1] Knapsack Problem and Subset Sum problem are NP complete and initially I figured this being similar would also be NP complete. However it differs since there is no relationship between the elements of a solution set of a Subset Sum problem. I was also unable to work out a reduction of any known NP-Complete problem to this problem.

The constraint on the solution set in the problem does not make it solvable in polynomial time. At best I can work out pseudo-polynomial time algorithms to solve this and the time blows up as K increases.

Am I right in suspecting this might be an NP-indeterminate problem or am I missing something?

PS: This is not homework. I am new at this and if this is not the right place for this question please advise and I shall move it. Thanks.

EDIT: After the discussions in the comments below I am providing a few examples towards what I am working on.

The above problem is trivial for the case where $d = 1$ and $n = 2$ for all $K$. It is easy when $K$ is even and for $d = 2$ and $n = 2$. I have been working on cases where $d = 2$ and $d = 4$ for $n \ge 3$ and didn't realise this.

For the case $K$ odd and $d = 2$, say $K = 65$ and I have $S = \{1,2,...,64\}$ and $S'= \{9,11,13,15,17\}$. The best algorithm I have for this takes time proportional to $\sqrt{K}$ and is thus exponential as $K$ grows.

For $K$ even, $d = 2$ and $n \ge 3$, say $K = 24$ I have $S'= \{3,5,7,9\}$.

I have found that when $K$ is odd or even then $|S|$ is odd or even respectively. I am trying to see if I can get a better algorithm to determine $S'$ or if I should concentrate elsewhere.

• If I understood the problem well (but probably not, because it seems too simple), it should be solvable in polynomial time: for every pair $(x_i,x_j)$ of elements in $S$ with $x_j>x_i$ check if $x_j−x_i$ is divisible by $K−1$; if yes then check if the points $x_i+t∗(x_j−x_i)/(K−1)$ are all contained in $S$ for $t=1,...,K−1$. One of the simplest NPC complete problem involving arithmetic progressions is (exact/minimum) set cover by arithmetic progression (but it is quite different from yours) – Marzio De Biasi Jun 26 '14 at 21:57
• I had made an error in the problem statement. I have fixed that now. Thanks for the heads up on exact cover by arithmetic progression, I was not aware of this. I am checking to see if it fits my problem. With respect to your answer I do not follow. For example with $K = 16$ we have $S = \{1,2,...,15\}$, there is no $S'$ where we may have $x_j - x_i$ divisible by $K-1$, since for all $x$ we have $x < K$. – gautam Jun 27 '14 at 3:24
• Is $n$ given? If not, then what stop me from taking $S'=\{1,K-1\}$. – Chao Xu Jun 27 '14 at 3:52
• After the correction to the question, if there are no restrictions on the unknown $n$ , the problem is (seems) still trivial: the set $S' = \{ K/2-1, K/2+1\}$ is always a solution for $K$ even, the set $S' = \{ \lfloor K/2 \rfloor, \lceil K/2 \rceil \}$ is always a solution for $K$ odd. In both case the solution has $n = 2$ elements. – Marzio De Biasi Jun 27 '14 at 6:58
• Aren't you free to choose $S'$? My interpertation: $S=\{1,2,3,4,5\}$, $S'=\{1,5\}\subset \{1,2,3,4,5\}$, $\sum S' = 1+5 = 6$. $d=4$ in this case. Also, the comment above seems to suggest $d$ is given in the input. If so, you might want to add it in your question. – Chao Xu Jun 27 '14 at 18:39

With some basic arithmetic, we can reduce this to a question about a two-variable Diophantine equation.

Based upon your comments, it sounds like $d$ was intended to be given as input. Now the question is just: can we choose $x_1 \ge 1$ and $n$ such that $x_1 + (n-1)d < K$ and such that the arithmetic sequence $x_1,x_1+d,x_1+2d,\dots,x_1+(n-1)d$ sums to $K$.

It is easy to compute the sum of this arithmetic sequence. By the Gauss formula, it sums to

$$n x_1 + dn(n-1)/2.$$

So, given $K,d$, we want to find a solution to the equation

$$n x_1 + dn(n-1)/2 = K$$

where $x_1,n$ are positive integers and where $x_1+ (n-1)d < K$.

You can view this as a diophantine equation in two variables $x,y$ of the form

$$2xy + \alpha x^2 + \beta x + \gamma = 0,$$

where $\alpha,\beta,\gamma$ are integer constants given in advance and there is an additional linear inequality on $x,y$. (Here I made the replacement $x=x_1$, $y=n$.) I don't know if this problem has a nice solution.

One thing we can say is that $n$ must be a divisor of $2K$, since we know

$$2nx_1 + dn(n-1) = 2K,$$

and the left-hand side is divisible by $n$. Therefore, if you know the factorization of $2K$, and if it doesn't have too many different prime divisors, you could try enumerating all divisors of $2K$ as the candidate values of $n$, and then for each candidate value of $n$, solve for $x_1$ and see if it yields an integral solution. However, in general this will not be efficient: it gives an algorithm that is efficient in the average case but runs in exponential time in the worst case.