Uniprocessor Feasibility of Sporadic Tasks Remains coNP-complete Under Bounded Utilization

Abstract—A central problem in real-time scheduling theory is to decide whether a sporadic task system with constrained deadlines is feasible on a preemptive uniprocessor. It is known that this problem is strongly coNP-complete in the general case, but also that there exists a pseudo-polynomial time solution for instances with utilization bounded from above by any constant c, where 0 < c < 1. For a long time it has been unknown whether the bounded case also has a polynomial-time solution. We show that for any choice of the constant c, such that 0 < c < 1, the bounded feasibility problem is (weakly) coNP-complete, and thus that no polynomial-time solution exists for it, unless P = NP. I