Compressed Subsequence Checking is PSPACE-complete

Abstract

It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is $\mathsf{PSPACE}$-complete, even over a binary alphabet. The lower bound is obtained by a polynomial-time reduction from quantified subset sum. If the two words are given explicitly, i.e., uncompressed, then the subsequence problem is hard for uniform ${\mathsf{NC}}^1$ and in deterministic logspace.