Strong inapproximability of the shortest reset word

Abstract

The Černý conjecture states that every $n$-state synchronizing automaton has a reset word of length at most $(n-1{)}^2$. We study the hardness of finding short reset words. It is known that the exact version of the problem, i.e., finding the shortest reset word, is NP-hard and coNP-hard, and complete for the DP class, and that approximating the length of the shortest reset word within a factor of $O(\log n)$ is NP-hard [Gerbush and Heeringa, CIAA'10], even for the binary alphabet [Berlinkov, DLT'13]. We significantly improve on these results by showing that, for every $\epsilon >0$, it is NP-hard to approximate the length of the shortest reset word within a factor of $n^{1-\epsilon }$. This is essentially tight since a simple $O(n)$-approximation algorithm exists.

extended abstract to appear in MFCS 2015