Can we convert an NFA to a regular expression of polynomial length?

Question

Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$?

In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\mathcal{O}(n)$-state NFA.

Answer 1

The answer to your question is negative. See the survey article

From Finite Automata to Regular Expressions and Back—A Summary on Descriptional Complexity by Hermann Gruber and Markus Holzer, Int. J. Found. Comput. Sci. 26(8): 1009-1040 (2015),

which contains a thorough discussion of your question. Let me quote in particular Theorem 24:

Let $n \geqslant 1$ and $\mathcal{A}$ be an $n$-state DFA or NFA over alphabet $\Sigma$. Then size $|\Sigma| \cdot 2^{\theta(n)}$ is sufficient and necessary in the worst case for a regular expression describing $L(\mathcal{A})$. This already holds for alphabets with at least two letters.