In this paper with the title of "NP-Complete Scheduling Problem" by J. D. Ullman, I am trying to understand the reduction from 3-SAT problem to a scheduling problem in order to prove the later is also np-complete. An instance of 3-SAT is given as below: enter image description here and this is the instance of the scheduling problem defined as: Single Execution Time Scheduling Problem with a variable number of processors. enter image description here

I can not totally understand the mapping between the two problems. Any hints that could help me getting the idea?


I see that you have posted this question before with no luck, and I think that this might be due to the amount of work needed to the answer such an open question. I looked at it also when you posted the first time, but needed a couple of hours to read through the proof and would have needed another couple of hours if I should have written a clear explanation for you (I know you are just asking for hints, but they are hard to give when I do not know which parts you already understand and which you don't). I at least, for one, would have been more inclined to write you an answer if you had asked more specific questions to the reductions, like e.g. what a role of a certain job is, or the like.

Also, your question does not contain all the info needed to answer, so one has to download the paper to find the relevant information oneself, and many people probably never go to that step, even when they are actually able to answer. You should have posted at least the definition of P4 and the time limits, and preferably also the example you posted in your last post, but with the explanation of the example and not just the table.

But, alas, after all this explanation of why you might not have gotten any answers, I really like these puzzle-y reductions so seeing that you posted again I made this little picture that can hopefully be of some help.

enter image description here

If you have questions after this, you are very welcome to write some (specific) questions, and I shall see if I can answer.

| cite | improve this answer | |

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.