#### Volume 21, issue 3 (2021)

 Recent Issues
 The Journal About the Journal Editorial Board Editorial Interests Subscriptions Submission Guidelines Submission Page Policies for Authors Ethics Statement ISSN (electronic): 1472-2739 ISSN (print): 1472-2747 Author Index To Appear Other MSP Journals
Coloring invariants of knots and links are often intractable

### Greg Kuperberg and Eric Samperton

Algebraic & Geometric Topology 21 (2021) 1479–1510
##### Abstract

Let $G$ be a nonabelian, simple group with a nontrivial conjugacy class $C\subseteq G\phantom{\rule{-0.17em}{0ex}}$. 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\phantom{\rule{-0.17em}{0ex}}$, the problem of counting homomorphisms ${\pi }_{1}\left({S}^{3}\setminus K\right)\to G$ that send meridians of $K$ to $C$ is almost parsimoniously $#\mathsf{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 $#\mathsf{P}$–complete. Where we previously used mapping class groups actions on closed, unmarked surfaces, we now use braid group actions.

##### Keywords
NP–hardness, \#P–hardness, knot invariants
##### Mathematical Subject Classification 2010
Primary: 20F10, 57M27, 68Q17