Exact algorithms improve smallest grammar problem complexity and hardness

Exact Algorithms and Complexity of the Smallest Grammar Problem

Data Structures and Algorithms

Summary

The smallest grammar problem looks for the shortest set of rules that can recreate a given string. The paper shows a new way to break down the problem that leads to faster exact algorithms for finding these grammars. It also proves that the problem is very hard (NP-complete) even when using just two letters. Additionally, limits on how fast the problem can be solved are established under standard complexity assumptions. The authors connect these findings to broader questions in computational complexity.

What this means in practice

  • For data compression engineers: Design more efficient algorithms to compress strings exactly by using faster methods for constructing minimal grammars.
  • For algorithm designers: Use the complexity bounds and the polynomial formulation to guide exact and approximate grammar-based compression algorithm development.

A theory result. No direct application yet.

Authors

Xiangle Chen

Abstract

The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, where size is the total length of the right-hand sides. Rules may be nested, so locally optimal choices of repeated fragments need not combine into an optimal grammar. We show that in an optimal grammar one can choose an occurrence of the expansion of each auxiliary nonterminal such that these intervals are pairwise disjoint. Hence the dictionary can be read off from a partition of the input, decoupling the choice of the dictionary from the parsing of rules. Using this property together with a bound on references to rules of length two, we obtain an exact algorithm running in $O^*(1.8723^n)$ time and $O(n)$ words of space, improving the $O^*(3^n)$ bound of Casel et al. for general grammars. For alphabet size $σ$ and $R=\log_σn$, we give a $2^{O((n/R)\log(R+1))}$-time algorithm, which is subexponential for fixed alphabets. Conversely, using an anchor-based projection from encoded grammars back to source grammars, we prove that SGP is NP-complete over a binary alphabet, answering a question of Casel et al., and construct instance families of tunable alphabet size on which no $2^{o(n/R)}n^{O(1)}$-time algorithm exists under ETH. Finally, for every $c>1$ we give a constant-degree integer polynomial formulation of SGP with $O(c^n)$ variables. By the barrier theorem of Belova, Golovnev, Kulikov, Mihajlin, and Sharipov, a proof that SGP is $λ^n$-SETH-hard under their deterministic fine-grained reductions would imply new lower bounds for Boolean series-parallel circuits or for arithmetic circuits.