Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Strong Inapproximability of the Shortest Reset Word
verfasst von : Paweł Gawrychowski, Damian Straszak
Erschienen in: Mathematical Foundations of Computer Science 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \(\mathrm {NP}\)-hard and \(\mathrm {coNP}\)-hard, and complete for the \(\mathrm {DP}\) class, and that approximating the length of the shortest reset word within a factor of \(O(\log n)\) is \(\mathrm {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 \(\varepsilon >0\), it is \(\mathrm {NP}\)-hard to approximate the length of the shortest reset word within a factor of \(n^{1-\varepsilon }\). This is essentially tight since a simple O(n)-approximation algorithm exists.