SLP (straight-line program) является контекстно-свободной грамматикой,
которая порождает единственное слово. Такую грамматику можно
рассматривать как сжатое описание слова. При этом длина порождаемого
слова может быть экспоненциально больше размера самой грамматики.
Некоторые свойства слов, задаваемых SLP грамматиками, можно быстро
проверить по грамматике, не вычисляя слово явным образом. Например,
проверка равенства двух слов, задаваемых своими SLP, может быть
проведена за время, полиномиально зависящее от размера грамматик.
Однако бывают и такое свойства, которые проверяются быстро, если
слова заданы явно (за полиномиальное от длины слова время), но
проверка свойства по SLP-описанию оказывается очень сложной задачей.
Например, задача проверки принадлежности слова автоматной грамматике
(по заданной SLP-грамматике) оказывается NP-полной, а задача подсчета
расстояния Хэмминга даже #P-полной.