How can we prove that Job Scheduling Problem with penalties is in NP?

How can we prove that Job Scheduling Problem with penalties is in NP开发者_运维技巧?

---

According to these course notes, reduction from Subset Sum can be used to show that Job Scheduling with penalties is also NP-complete.

---

The standard nondeterministic approach ("guess then check") should work here: Guess how the jobs should be scheduled, then check that this schedule comes in under the penalty limit (which is obviously possible in polynomial time).

Usually, showing that a problem is in NP is relatively easy -- the harder part is showing that it is also NP-complete (but in this case, you don't seem to need to do that).