Abstract
We prove that a special case of the NP-complete problem Multiprocessor Scheduling (MPS) is in P. In particular, we prove that given 〈r, m〉, where r ∈ ℕ and m ∈ ℕ⁺, deciding whether or not it is possible to partition the set Sᵣ = {0, 1,..., r} into m subsets summing to the same, can be done in time O(|r|²). By using the fact that the partitioning problem belongs to P, we prove that a related graph problem resides in the same complexity class.