When the running time of a smallest grammar algorithm is $O(|\Sigma|^{\log_2(|s|)})$ for input $s$.

Question

Suppose I could prove that the running time of a smallest grammr algorithm were $O(|\Sigma|^{\log_2(|s|)})$. Then is that considered a polynomial-time algorithm, or exponential in the context of the $P = NP$ problem?

$\Sigma = $ the minimal alphabet of $s$.

I'm looking for someone who has a link or can explain how they showed that smallest grammar problem is NP-complete. When they showed this, did they consider a fixed alphabet size, and it is NP-complete with respect to input length $|s|$ only? Or...

Answer 1

Remember that $a^{\log(b)}= b^{\log(a)}$. Thus we have:

$$O(|\Sigma|^{\log_2(|s|)}) = O(|s|^{\log_2(|\Sigma|)})$$

In other words, as long as either the alphabet or the size of the $s$ does not grow without bound, your algorithm is polynomial complexity, as the exponent will simply be constant.