EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard.

Friedrich Eisenbrand, Thomas Rothvo

Browse the full SODA paper archive.