Coloring invariants of knots and links are often intractable

Kuperberg, Greg; Samperton, Eric

doi:10.2140/agt.2021.21.1479

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the Journal

Editorial Board

Subscriptions

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1472-2739 (online)

ISSN 1472-2747 (print)

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

DOI: 10.2140/agt.2021.21.1479

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 $π_{1} (S^{3} ∖ 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.

Keywords

NP–hardness, \#P–hardness, knot invariants

Mathematical Subject Classification 2010

Primary: 20F10, 57M27, 68Q17

References

Publication

Received: 20 November 2019

Revised: 6 September 2020

Accepted: 22 September 2020

Published: 11 August 2021

Authors

Greg Kuperberg
Department of Mathematics University of California, Davis Davis, CA United States

Eric Samperton
Department of Mathematics University of Illinois at Urbana-Champaign Urbana, IL United States

Volume 21, issue 3 (2021)