Skip to content
Log in
Sponsored AI Networking Cookbook: Practical recipes for AI-assisted network automation and development AI Networking Cookbook: Practical recipes for AI-assisted network automation and development
Preprint

Compressed Subsequence Checking is PSPACE-complete

Markus Lohrey
Sep 2026 · 0 citations · 15 references
Computer Science

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.

arXiv Semantic Scholar
View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.