arXiv preprint ·
The Complexity of Value Optimization in Sporadic Task Systems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Impossibility of No-Regret in Multi-Agent Bidding
Linear Hashing Is Poissonesque
Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set
Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.