On two algorithmic problems about synchronizing automata (Short Paper)

Abstract

Under the assumption P=NP, we prove that two natural problems from the theory of synchronizing automata cannot be solved in polynomial time. The first problem is to decide whether a given reachable partial automaton is synchronizing. The second one is, given an n-state binary complete synchronizing automaton, to compute its reset threshold within performance ratio less than d ln (n) for a specific constant d>0. © 2014 Springer International Publishing Switzerland.