  Workflow nets are a popular variant of Petri nets that allow for algorithmic
formal analysis of business processes. The central decision problems concerning
workflow nets deal with soundness, where the initial and final configurations
are specified. Intuitively, soundness states that from every reachable
configuration one can reach the final configuration. We settle the widely open
complexity of the three main variants of soundness: classical, structural and
generalised soundness. The first two are EXPSPACE-complete, and, surprisingly,
the latter is PSPACE-complete, thus computationally simpler.
