This question is based on the slides from this pdf:

  • Slide 54, they define the Subset Sum Problem.

  • Slide 65, they define the Partition problem.

  • Slide 74, they talk about the Job Scheduling problem.

My question is, is it possible to cut the middle man of the partition problem and reduce Subset Sum to Job Scheduling directly?

To prove scheduling is NP, we can use what is already stated since it's not related to partition.

I'm not sure how to combine the reduction from both onto one though.

  • $\begingroup$ are you asking about the reduction itself? $\endgroup$ – lox Mar 25 '19 at 20:48
  • $\begingroup$ Yeah, reducing from Subset Sum to Job Scheduling basically. $\endgroup$ – Andrew Raleigh Mar 25 '19 at 20:49

Yes, that's possible.

The reduction from Subset Sum to Partition is a mapping $f$ from Subset-Sum-instances to Partition-instances. The reduction from Partition to Job Scheduling is a mapping $g$ from Partition-instances to Job-Scheduling-instances. So, the function $g \circ f$ is a mapping from Subset-Sum-instances to Partition instances.

This gives you a direct reduction in one step; the reduction is given by the function $g \circ f$. If you work through the details of the construction of $f$ and $g$, you should be able to figure out what $g \circ f$ is doing. If you wanted, you could write down the definition of the function $g \circ f$ without telling anyone that it came from composing $f$ and $g$. Whether that would be useful in any way is a different question...


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.