Determining the reset threshold is computationally hard.
The decision problem, whether the reset threshold is smaller than a given integer, is NP-complete [1]}, and it remains hard even for very restrictive classes such as binary Eulerian automata [2]}.
The functional problems of computing the reset threshold and a shortest reset word are respectively \(\mathrm {FP}^{\mathrm {NP}[\log ]}\) -complete and \(\mathrm {FP}^{\mathrm {NP}}\) -complete [3]}.
Moreover, approximating the reset threshold is hard even for approximation factors in \(\mathcal {O}(n^{1-\varepsilon })\) , for every \(\varepsilon > 0\)  [4]}.
This inapproximatibility also holds for subclasses related to prefix codes [5]}.
On the other hand, there exists a simple general \(\mathcal {O}(n)\) -approximating polynomial algorithm [6]}.
It is open whether there exists a polynomial algorithm approximating within some sublinear factor, e.g., in \(\mathcal {O}(n/\log n)\) .
