The paper shows a theoretical complexity of the problem of verifying nested workflows with additional precedence, synchronization, and logical constraints.