I have to show that the following problem is NP-Complete and need some helpful hints on how to proceed.
The problem:
We're looking at a meeting booking system. The input is a list n of possible times as well as m lists (where m <= n), one list per person containing their choice of possible meeting times. For each possible time, a priority number is also given. For each reservation time in the list of n, a cost is also given. (Cost of booking the room). The algorithm should assign times so that the combined priority for those who have booked should be as small as possible while the total cost of booking should not be higher than M.
NP
So first to show that it's in NP we should show that given a correct solution it can be verified that it is indeed correct. I guess it should verify that that the cost is below the threshold of K and that the priority of the correct solution is indeed the minimum - both of which can be done in Polynomial time I assume. We traverse through the lists of people, assert that each one has a time granted to them, add up the cost in a variable and at the end of this list assert that the cost is below K. The priority can be dealt with in similar fashion I suppose?
NP Hard
Then to show it's NP Hard I can use the Knapsack Problem since they're rather similar. With input S, size of bag, a list of items with weight w and value v as well as the goal W which is the goal-value. I guess it's clear that S can correlate to cost and that W correlate to the priority? So we want S, the size, to be below S i.e we have the similar condition for the problem above where the cost has to be below K. Then W, the total value should generally exceed W, but in our case we want it to be as low as possible which seems doable.
I'm afraid I might've gone the wrong way when it comes to verifying the problem. Also the reduction to show it's NP Hard is perhaps not thought out all the way. Some pointers would be very helpful! Thanks
NP
When you are proving the problem is in NP, you must first turn your problem into a decision problem. Then you can verify your certificate in polynomial time as you started to describe.
NP Hard
You need to transform the Knapsack problem into your meeting problem. You are going the right way because you are transforming size and weight from Knapsack into the meeting problem. Once you figure out the transformation, you must verify that it can be done in polynomial time. Finally, you can show that the solution to Knapsack is a solution to meeting problem and vice versa.