NP-completeness: P, NP, reductions
Design and Analysis of Algorithms · Engineering
Study notes
Show scheduling is NP-complete: reduce from known NP-complete partition problem by mapping each number to a job duration. If the scheduler could split jobs evenly in polynomial time, it would solve partition too. So efficient scheduling is as hard as the hardest NP problems.