Volume 21, issue 3 (2021)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 22
Issue 5, 2007–2532
Issue 4, 1497–2006
Issue 3, 991–1495
Issue 2, 473–990
Issue 1, 1–472

Volume 21, 7 issues

Volume 20, 7 issues

Volume 19, 7 issues

Volume 18, 7 issues

Volume 17, 6 issues

Volume 16, 6 issues

Volume 15, 6 issues

Volume 14, 6 issues

Volume 13, 6 issues

Volume 12, 4 issues

Volume 11, 5 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 4 issues

Volume 7, 4 issues

Volume 6, 5 issues

Volume 5, 4 issues

Volume 4, 2 issues

Volume 3, 2 issues

Volume 2, 2 issues

Volume 1, 2 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 G. Let K be a diagram of an oriented knot in S3, thought of as computational input. We show that for each such G and C, the problem of counting homomorphisms π1(S3 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.

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