Coloring invariants of knots and links are often intractable

Abstract

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 show that for each such $G$ and $C$, the problem of counting homomorphisms ${\pi }_1(S^3\setminus K)\to G$ that send meridians of $K$ to $C$ is almost parsimoniously $\#P$-complete. This work is a sequel to a previous result by the authors that counting homomorphisms from fundamental groups of integer homology 3-spheres to $G$ is almost parsimoniously $\#P$-complete. Where we previously used mapping class groups actions on closed, unmarked surfaces, we now use braid group actions.

14 pages, 6 figures

References in corpus (3)

• Models of Random Knots
• Schur-type invariants of branched G-covers of surfaces
• Computational complexity and 3-manifolds and zombies

Cited by in corpus (2)

• Computational complexity and 3-manifolds and zombies
• Topological quantum computation is hyperbolic