Coloring invariants of knots and links are often intractable
arXiv:1907.05981 · doi:10.2140/agt.2021.21.1479
Abstract
Let be a nonabelian, simple group with a nontrivial conjugacy class . Let be a diagram of an oriented knot in , thought of as computational input. We show that for each such and , the problem of counting homomorphisms that send meridians of to is almost parsimoniously -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 is almost parsimoniously -complete. Where we previously used mapping class groups actions on closed, unmarked surfaces, we now use braid group actions.
arXiv comment14 pages, 6 figures
References in corpus (7)
- Strengths and Weaknesses of Quantum Computing
- Finite covers of random 3-manifolds
- Models of Random Knots
- Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
- Schur-type invariants of branched G-covers of surfaces
- Hurwitz Monodromy and Full Number Fields
- Computational complexity and 3-manifolds and zombies