Skip to main content
Computer Science

Return to Question

Post Timeline

trying to be more explicit.
Source Link
tkellehe
tkellehe
  • 157
  • 6

Problem

Given a range of numbersintegers $[a,...,b]$$\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?

Problem

Given a range of numbers $[a,...,b]$, find a subset of size $k$ such that the sum is equal to $s$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?

Problem

Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?

Source Link
tkellehe
tkellehe
  • 157
  • 6

Check if K-Sum Variation is NP-Complete

Problem

Given a range of numbers $[a,...,b]$, find a subset of size $k$ such that the sum is equal to $s$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?