Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

The very first sentence of the paper defines what problem they are considering:

This paper addresses the smallest grammar problem; namely, what is the smallest context-free grammar that generates exactly one given string?

share|cite|improve this answer
The problem they also deal with is whether an algorithm in P exists that finds a smallest grammar. I would be assuming that they mean treating the alphabet size as a constant. It seems like a reasonable assumption, since when we want the smallest grammar of something, we usually fix the alphabet. But I'm still not 100% convinced they mean that. – Enjoys Math Apr 17 '12 at 19:07
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
That's right. I knew that, but the thought bubbled up again, and I need to think before I shoot questions to the forums. If an algorithm is bounded by a polynomial in the alphabet size of s, then it is also bounded polynomially in the size of s. – Enjoys Math Apr 17 '12 at 19:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.