Uniprocessor Feasibility of Sporadic Tasks Remains coNP-complete Under Bounded Utilization
2015 (English)Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
, Real-Time Systems Symposium-Proceedings, ISSN 1052-8725
Research subject Computer Science with specialization in Real Time Systems
IdentifiersURN: urn:nbn:se:uu:diva-265784DOI: 10.1109/RTSS.2015.16ISI: 000380424600009ISBN: 9781467395076OAI: oai:DiVA.org:uu-265784DiVA: diva2:866563
The 36th IEEE Real-Time Systems Symposium (RTSS)