Exact Algorithms and Complexity of the Smallest Grammar Problem

Overview & Synopsis

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.