Coloring invariants of knots and links are often intractable
share
Let G be a nonabelian, simple group with a nontrivial conjugacy class C ⊆ 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 π_1(S^3∖ K) → 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.
READ FULL TEXT