2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Jun 26 '14 at 21:57
  • $\begingroup$ 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$. $\endgroup$ – gautam Jun 27 '14 at 3:24
  • $\begingroup$ Is $n$ given? If not, then what stop me from taking $S'=\{1,K-1\}$. $\endgroup$ – Chao Xu Jun 27 '14 at 3:52
  • 4
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Jun 27 '14 at 6:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Chao Xu Jun 27 '14 at 18:39
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.