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

<p>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 &lt; K$ and such that the arithmetic sequence $x_1,x_1+d,x_1+2d,\dots,x_1+(n-1)d$ sums to $K$.</p>

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

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

<p>So, given $K,d$, we want to find a solution to the equation</p>

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

<p>where $x_1,n$ are positive integers and where $x_1+ (n-1)d &lt; K$.</p>

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

<p>$$2xy + \alpha x^2 + \beta x + \gamma = 0,$$</p>

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

<p>One thing we <em>can</em> say is that $n$ must be a divisor of $2K$, since we know</p>

<p>$$2nx_1 + dn(n-1) = 2K,$$</p>

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

CC BY-SA 3.0
2014-06-27T19:17:47.353Z
2014-06-27T19:26:26.890Z
2014-06-27T19:26:26.890Z
D.W.
<p>What could be the complexity class of the following problem: <br> 
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$.</p>

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

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

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

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

<p><i>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.</i></p>

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

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

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

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

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

CC BY-SA 3.0
2014-06-26T21:57:38.823Z
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
CC BY-SA 3.0
2014-06-27T03:24:27.160Z
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
CC BY-SA 3.0
2014-06-27T03:52:08.610Z
Is $n$ given? If not, then what stop me from taking $S'=\{1,K-1\}$.
Chao Xu
CC BY-SA 3.0
2014-06-27T04:10:04.563Z
If $n$ is given, then you can model this as a constant dimension integer program, which is solvable in linear time.
Chao Xu
CC BY-SA 3.0
2014-06-27T05:16:56.830Z
$n$ is not known. For $S'= \{1,2...,K-1\}$ the sum of all elements will not be equal to $K$.
gautam
CC BY-SA 3.0
2014-06-27T05:35:42.280Z
The set $S'=\{1,K-1\}$ has all the properties you prescribed.
Chao Xu
CC BY-SA 3.0
2014-06-27T06:58:57.983Z
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
CC BY-SA 3.0
2014-06-27T17:30:02.123Z
@Marzio thanks. I have actually been working on this problem for $d = 2$ and $d = 4$ and never considered $d = 1$. I will try to work out if I can extend the solution for $d = 1$ to $d = 2$ or $d = 3$ or $d = 4$.
gautam
CC BY-SA 3.0
2014-06-27T17:34:46.103Z
@Chao. Thanks, can you please elaborate. For $K = 6$, $S$ will be $\{1,2,3,4,5\}$ and as per your clarification we get $S'= \{1,2,3,4,5\}$ as $(K-1) = 5$, so $S = S'$. Also $\sum{S} = 15$, whereas $K = 6$.
gautam
CC BY-SA 3.0
2014-06-27T18:39:27.840Z
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
CC BY-SA 3.0
2014-06-27T18:52:52.950Z
@Chao. Thanks, got it. Yes we are free to choose $S'$ but $d$ is  set in advance, generally 2 or higher. It cannot be chosen as part of the solution. I'll update this in the problem statement. Appreciate this. I get so wrapped up in what I work on that I miss some of these.
gautam
<np-hardness><complexity-classes><subset-sum>
Complexity class of a subset problem similar to subset sum
gautam
# Complexity class of a subset problem similar to subset sum

(Asked by: username_0 on 2014-06-26)

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.

**Tags:** np-hardness, complexity-classes, subset-sum
> **Comments:**
> **username_1**: 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)  
> **username_0**: 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$.  
> **username_2**: Is $n$ given? If not, then what stop me from taking $S'=\{1,K-1\}$.  
> **username_2**: If $n$ is given, then you can model this as a constant dimension integer program, which is solvable in linear time.  
> **username_0**: $n$ is not known. For $S'= \{1,2...,K-1\}$ the sum of all elements will not be equal to $K$.  
> **username_2**: The set $S'=\{1,K-1\}$ has all the properties you prescribed.  
> **username_1**: 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.  
> **username_0**: @Marzio thanks. I have actually been working on this problem for $d = 2$ and $d = 4$ and never considered $d = 1$. I will try to work out if I can extend the solution for $d = 1$ to $d = 2$ or $d = 3$ or $d = 4$.  
> **username_0**: @Chao. Thanks, can you please elaborate. For $K = 6$, $S$ will be $\{1,2,3,4,5\}$ and as per your clarification we get $S'= \{1,2,3,4,5\}$ as $(K-1) = 5$, so $S = S'$. Also $\sum{S} = 15$, whereas $K = 6$.  
> **username_2**: 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.  
> **username_0**: @Chao. Thanks, got it. Yes we are free to choose $S'$ but $d$ is  set in advance, generally 2 or higher. It cannot be chosen as part of the solution. I'll update this in the problem statement. Appreciate this. I get so wrapped up in what I work on that I miss some of these.  

---

## 1 answers

### Answer by username_3 on 2014-06-27. Score: 0 | Accepted answer

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.


---

