Problem: given a set of n tasks with execution time Ti, due date Di, and a profit Vi (given only if is enden before due date), is there a task schedule that returns a total profit greater or equal than k knowing that tasks must be executed one at a time?

I am asked to proof that this problem is NP-Complete, can anyone help?



Since this problem is very approachable, you could first try to think about a greedy solution to show this is in the class P, and thus probably not in NP-complete. Once you have done this you could think about a polytime reduction to a problem known to be in NP-complete. Consult Karp's original 21 problems to get a feel for the type of problems you can use to find this reduction. Once you have done this come back with more specific questions :)

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