Coloring invariants of knots and links are often intractable

Greg Kuperberg, Eric Samperton

Let $G$ be a nonabelian, simple group with a nontrivial conjugacy class $C\subseteq G$. Let $K$ be a diagram of an oriented knot in $S^3$, thought of as computational input. We sh…