Volume 21, issue 3 (2021)

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

Volume 21
Issue 4, 1595–2140
Issue 3, 1075–1593
Issue 2, 543–1074
Issue 1, 1–541

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