Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete
2015 (English)In: Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS), 2015, 281-286 p.Conference paper (Refereed)
Deciding the feasibility of a sporadic task system on a preemptive uniprocessor is a central problem in real-time scheduling theory. The computational complexity of this problem has been a long-standing open question. We show that it is coNP-complete in the strong sense, even when deadlines are constrained. This is achieved by means of a pseudo-polynomial transformation from the strongly NP-hard Simultaneous Congruences Problem to the complement of the feasibility problem.
Place, publisher, year, edition, pages
2015. 281-286 p.
, Euromicro Workshop on Real-Time Systems-Proceedings, 1068-3070
Research subject Computer Science with specialization in Real Time Systems
IdentifiersURN: urn:nbn:se:uu:diva-265783DOI: 10.1109/ECRTS.2015.32ISI: 000375052900025OAI: oai:DiVA.org:uu-265783DiVA: diva2:866561
The 27th Euromicro Conference on Real-Time Systems (ECRTS)