Complexity of optimizing task selection in real time systems
The Complexity of Value Optimization in Sporadic Task Systems
Computational ComplexityData Structures and Algorithms
Summary
This paper studies how hard it is to pick the best set of tasks to run on a single processor in real time while meeting all deadlines and reaching a target value. The authors show that deciding if such a selection exists is very complex, falling into a class called Σ₂^P-complete, meaning it involves layers of possible and necessary conditions. They use advanced math and logic tools to prove this complexity even when tasks have simple numerical descriptions. This finding means that automatic scheduling for value in these systems is inherently difficult.
What this means in practice
- •For real-time system developers: Assess the feasibility and limitations of algorithms that optimize task selection with deadlines and values in embedded real-time systems.
- •For operating system schedulers: Understand fundamental complexity barriers when designing schedulers that must guarantee deadlines while maximizing task value in single-core processors.
A theory result. No direct application yet.
Authors
Christopher Harbourne, Nathan Fisher, Kecheng Yang, Pontus Ekberg, Sanjoy Baruah, Zhishan Guo
Abstract
Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline. We study its threshold decision form for finite collections of independent sporadic tasks scheduled preemptively on one processor. We prove that this problem is $Σ_2^P$-complete for both constrained and arbitrary deadlines, even when all numerical parameters are encoded in unary. The existential choice is the selected task set, while the universal condition requires every processor-demand window to remain feasible. Our hardness reduction already uses constrained-deadline tasks. It represents universal assignments by Chinese Remainder Theorem timestamps and uses polynomial-weight local selector locks to enforce a valid existential assignment. The reduction produces polynomially many tasks, and every generated execution time, deadline, period, task value, and target is polynomially bounded in the source-instance size.