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.
Supported by the NCN grant 2011/01/D/ST6/07164.
P. Gawrychowski—Currently holding a post-doctoral position at Warsaw Center of Mathematics and Computer Science.
D. Straszak—Part of the work was carried out while the author was a student at Institute of Computer Science, University of Wrocław, Poland.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Amortized free bit complexity is a parameter of a PCP verifier which essentially corresponds to the ratio between the free bit complexity and the logarithm of error probability.
References
Ananichev, D.S., Volkov, M.V.: Synchronizing generalized monotonic automata. Theor. Comput. Sci. 330(1), 3–13 (2005)
Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, Cambridge (2009)
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998)
Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998)
Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability–towards tight results. SIAM J. Comput. 27, 804–915 (1998)
Berlinkov, M.V.: Approximating the minimum length of synchronizing words is hard. Theor. Comp. Sys. 54(2), 211–223 (2014)
Berlinkov, M.V.: On two algorithmic problems about synchronizing automata. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 61–67. Springer, Heidelberg (2014)
Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19, 500–510 (1990)
Feige, U.: A threshold of \(\ln n\) for approximating set cover. J. ACM 45(4), 634–652 (1998)
Gerbush, M., Heeringa, B.: Approximating minimum reset sequences. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol. 6482, pp. 154–162. Springer, Heidelberg (2011)
Grech, M., Kisielewicz, A.: The Černý conjecture for automata respecting intervals of a directed graph. Discrete Mathematics & Theoretical Computer Science 15(3), 61–72 (2013)
Hastad, J.: Clique is hard to approximate within \(n^{1-\epsilon }\). In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, pp. 627–636 (1996)
Hastad, J., Khot, S.: Query efficient PCPs with perfect completeness. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 610–619, October 2001
Kari, J.: Synchronizing finite automata on Eulerian digraphs. Theor. Comput. Sci. 295, 223–232 (2003)
Olschewski, J., Ummels, M.: The complexity of finding reset words in finite automata. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 568–579. Springer, Heidelberg (2010)
Pin, J.: On two combinatorial problems arising from automata theory. In: Combinatorial Mathematics Proceedings of the International Colloquium on Graph Theory and Combinatorics, vol. 75, pp. 535–548. North-Holland (1983)
Rystsov, I.: Reset words for commutative and solvable automata. Theor. Comput. Sci. 172(1–2), 273–279 (1997)
Steinberg, B.: The Černý conjecture for one-cluster automata with prime length cycle. Theor. Comput. Sci. 412(39), 5487–5491 (2011)
Volkov, M.V.: Synchronizing automata and the Černý conjecture. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11–27. Springer, Heidelberg (2008)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 681–690 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gawrychowski, P., Straszak, D. (2015). Strong Inapproximability of the Shortest Reset Word. In: Italiano, G., Pighizzini, G., Sannella, D. (eds) Mathematical Foundations of Computer Science 2015. MFCS 2015. Lecture Notes in Computer Science(), vol 9234. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48057-1_19
Download citation
DOI: https://doi.org/10.1007/978-3-662-48057-1_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48056-4
Online ISBN: 978-3-662-48057-1
eBook Packages: Computer ScienceComputer Science (R0)