Feasibility analysis of recurrent DAG tasks is PSPACE-hard
Vincenzo Bonifaci, Alberto Marchetti-Spaccamela · Theoretical Computer Science · 2025
We study a popular task model for scheduling parallel real-time tasks, where the internal parallelism of each task is modeled by a directed acyclic graph (DAG). We show that deciding the feasibility of a set of sporadically recurrent DAG tasks is hard for the complexity class PSPACE , thus ruling out approaches to this problem that rely on Integer Linear Programming or Satisfiability solvers (assuming NP ≠ PSPACE ).