On calculating length of minimal synchronizing words
Mikhail V. Berlinkov · arXiv (Cornell University) · 2009
The famous \v{C}ern\'y conjecture claims that each $n$-state synchronizing automaton $\mathrsfs{A}$ has a reset word of length at most $(n-1)^2$. The best upper bound for the minimum length of reset word for $\mathrsfs{A}$ known so far is a cubic polynomial of $n$. So the problem of searching length of a shortest word is of certain importance. This problem is $NP$-complete. However, the algorithmic problem of approximation length of a minimal reset word is still open. Gawrychowski proved that this problem is $NP$-complete for the error 2. We present an independent result for any positive error. It means that we prove that the approximation problem of searching the length of a shortest reset word is $NP$-complete. Moreover, we show it is true in the case of 2-letter alphabet.