I’m having a hard time figuring out how to reduce a problem to prove that it is NP-complete.
Basically, my problem is this:
The Test Scheduling problem is faced by testers. They have a bunch of >ideas for tests, each of which would require some machine. Unfortunately, >each machine can only be used for a single test. The problem takes the >list of tests for each test and asks whether n of the tests can be >performed simultaneously.
Show that test scheduling is NP-complete by showing it is in NP and reduce >it from a known NP-Complete problem
What will be my certificate, and how can i develop the CNF formula to represent this problem?