0
$\begingroup$

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

1 Answers 1

1

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?

  • 0
    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.2012-04-17