Shortest common superstrings
OpenAI's polynomial-time algorithm (2026) that finds a common superstring at most twice as long as the shortest one, for every finite family of strings. Forced occurrence counts give a balanced graph of cost at most the optimum; periodic layers and a rule for periodic words show how to connect it at no more than the same cost again.
Four lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.
Theorems and assumptions · Reader and editable sources · Course record
Prerequisites
- Strings, substrings and lexicographic order; directed multigraphs.