Embedded Files
To show that the problem of course allocation is NP-Complete, we need to show that it lies in the NP complexity class, and that any other NP-Hard Problem can reduce to it.
Course Allocation ∈ NP if there exists an efficient algorithm to verify the correctness of a solution allocation. We can check that a course allocation is valid by checking that a student is in no more than one course at the same time, and that all courses do not exceed the allowed number of seats. Since the work to check each student and course will only grow linearly with the number of students and courses, we know our verification algorithm is efficient and the problem of course allocation is in NP.
Course Allocation ∈ NP-Hard. We can either show that there exists a polynomial time reduction from every problem A ∈ NP to it, or we can show that there exists a polynomial time reduction from a known NP-Hard Problem.
Credit for slide format: Professor Hott
We can reduce knapsack to course allocation in polynomial time.
- We can map each knapsack (item, value) pair to a (student, number of seats) pair, transforming any instance of knapsack to a course allocation problem with one class slot.
- If we assume that our problem can be solved in polynomial time, then we can map a solution to our problem back to the knapsack problem. The students chosen for the class correspond to the items chosen to fill the backpack
- Since we know the knap-sack cannot be solved with a polynomial time algorithm, we reach a contradiction and our assumption that our problem could be solved with a in polynomial time algorithm must be false.
Since the course allocation problem is in NP and NP-Hard, we can conclude that it lies within the NP-Complete complexity class.
This classification guides our strategies for solving the problem. Knowing that a brute force approach would not scale to any practical situation, we look to heuristics to find optimal or near-optimal solutions to our problem.
Report abuse