Rate-Monotonic Schedulability of Implicit-Deadline Tasks is NP-hard Beyond Liu and Layland's Bound

We study the computational complexity of the Fixed-Priority (FP) schedulability problem for sporadic or synchronous periodic tasks with implicit deadlines on a single preemptive processor. This problem is known to be (weakly) NP-complete in the general case, but Liu and Layland's classic utilization bound trivially provides a polynomial-time solution for task sets with Rate-Monotonic (RM) priorities and utilization bounded from above by ln(2), or approximately 69%. Here we show that ln(2) is in fact the sharp boundary between computationally easy and hard schedulability testing: The FP-schedulability problem is NP-complete even if restricted to task sets with RM priorities and utilization bounded from above by any constant c > ln(2). This disproves a conjecture by Rothvoß. Further, we show that if a non-RM priority ordering can be specified, then the FP-schedulability problem is NP-complete already when utilization is bounded by any constant c > 0.