# Question about the Smallest Grammar problem.

Is the problem to prove whether or not there exists an algorithm with running time polynomial in the length of the input string $|s|$, or polynomial both in $|s|$ and the size of the alphabet $|A|$ ? The papers I'm looking at assume that you know which one they mean.

Edit: Paper

-

Well, the alphabet can trivially be taken to be the set of symbols found in the input string, or you could fix it as $\{0,1\}$. I assume that one would allow any number of nonterminals in the grammar; more than $|s|$ of them will never be optimal anyway. –  Henning Makholm Apr 17 '12 at 19:11