Approximating the Minimum Length of Synchronizing Words Is Hard

摘要

We prove that, unless P = NP, no polynomial-time algorithm can approximate the minimum length of reset words for a given synchronizing automaton within a constant factor.