An optimal alignment consists of a minimal number of edit operations (deletions and insertions) to fit an observed event trace with a process model. In conformance checking, alignments are used to quantify in how far reality deviates from the predefined business norm and constitute probably the most important tool. In practice, however, it has frequently been observed that finding optimal alignments is computationally expensive. In this paper, we extend the proof of the Shortest Sequence Theorem for live, bounded, free-choice Petri nets to make it also applicable to moves in alignments on this model class. This way, we are able to show that computing alignments on sound free-choice workflow nets is NP-complete. While this still rules out an efficient algorithm, our result opens the door for a new set of tools to attack the alignment problem which go beyond the standard reachability approach used in most implementations. Eventually, we will demonstrate that soundness alone is not a sufficient criterion by proving that computing alignments on general safe and sound workflow nets is PSPACE-complete and thus indeed incurring immense algorithmic costs on more general model classes.