Compressed subsequence checking is computationally hard even on two letters
Compressed Subsequence Checking is PSPACE-complete
Formal Languages and Automata Theory
Summary
The problem of checking if one sequence appears scattered within another can be tricky when the sequences are stored in compressed forms. The authors show that deciding this is as tough as the hardest problems known in a complexity class called PSPACE, meaning it likely requires a lot of computational resources. This holds true even when the sequences only use two letters. They reached this conclusion by relating the problem to a well-known challenging problem called quantified subset sum.
What this means in practice
- •For software engineers: Understand the computational limits when working with compressed text patterns to avoid inefficient solutions that may not scale.
- •For database system designers: Design indexing and search systems that account for the high complexity of subsequence queries on compressed data representations.
A theory result. No direct application yet.
Authors
Markus Lohrey
Abstract
It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is PSPACE-complete, even over a binary alphabet. The lower bound is obtained by a polynomial-time reduction from quantified subset sum.