On the Complexity of Resource Controllability in Business Process Management

Resource controllability of business processes (BPs) is the problem of executing a BP by assigning resources to tasks, while satisfying a set of constraints, according to the outcome of a few uncontrollable events that we only observe during execution. Recent research addressed resource controllability of acyclic BPs where the choices of the XOR paths to take were out of control. However, a formal model of BP to reason on resource controllability is still missing. Thus, the precise mathematical definitions of controllability problems, their semantics and complexity analysis, have remained unexplored. To bridge this gap, we propose a hierarchy of 8 classes of Business Processes with Resources and Uncertainty (BPRUs) to address controllable and uncontrollable resource assignments in combination with controllable and uncontrollable choices of the XOR paths to take. We define consistency of BPRs (i.e., BPRUs without uncertainty) and prove that deciding it is NP-complete. We define strong controllability of BPRUs and prove that deciding it is either NP-complete or Σ2p -complete depending on the class. We define weak and dynamic controllability of BPRUs and prove that deciding them is Π2p -complete and PSPACE-complete, respectively.