Circuit Complexity of Shuffle

We show that Shuffle(x,y,w), the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y, is not in AC0, but it is in AC1. The fact that shuffle is not in AC0 is shown by a reduction of parity to shuffle and invoking the seminal result [FSS84, while the fact that it is in AC1 is implicit in the results of [Man82a]. Together, the two results provide a strong complexity bound for this combinatorial problem.