Coloring invariants of knots and links are often intractable (Q1983547)

One of the main problems in knot theory is the knot recognition problem. The essence of this problem is to construct an effective algorithm that determines by two given knots whether they are equivalent or not. One possible approach to this problem is to construct invariants, i.e. such functions that have the same value on equivalent knots. If we manage to find an invariant \(f\) such that \(f(K_1)\neq f(K_2)\), then we can conclude that \(K_1\) and \(K_2\) are non-equivalent knots. One of the simplest invariants in knot theory is the \(3\)-coloring invariant of the diagram which is also called the Fox coloring. This invariant is not very strong, i.e. it can be the same for a lot of different knots. However, it allows to distinguish the trefoil knot from the trivial knot and from the figure-eight knot. More complex invariants are the knot group and the knot quandle. These invariants are very strong (in particular, the knot quandle defines a knot up to simultaneous change of orientation and mirror reflection), however, in order to use these invariants one must be able to solve the isomorphism problem for groups or the isomorphism problem for quandles. In [\textit{A. D. Brooke-Taylor} and \textit{S. K. Miller}, J. Aust. Math. Soc. 108, No. 2, 262--277 (2020; Zbl 1482.20039)] it is shown that the isomorphism problem for quandles is, from the perspective of Borel reducibility, fundamentally difficult (Borel complete). The invariant \(|Q(K;G,C)|\), where \(K\) is a knot, \(G\) is a nonabelian finite simple group, \(C\) is a generating conjugacy class in \(G\), is a kind of intermediate between the knot group and the knot coloring. The value of this invariant on a knot \(K\) is equal to the number of elements in the quotient of the set of surjective homomorphisms from the group \(G(K)\) of knot \(K\) to the group \(G\) such that the images of the Wirtinger generators of the group \(G(K)\) belong to \(C\), by the group \(\mathrm{Aut}(G,C)\) of automorphisms of \(G\) which fix \(C\). The authors of the paper under review prove that the problem of computing the invariant \(|Q(K;G,C)|\) for a given group \(G\) and its conjugcay class \(C\) is parsimoniously \(\#P\)-complete.