Volume 21, issue 3 (2021)

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

Volume 24
Issue 4, 1809–2387
Issue 3, 1225–1808
Issue 2, 595–1223
Issue 1, 1–594

Volume 23, 9 issues

Volume 22, 8 issues

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
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Author Index
To Appear
Other MSP Journals
This article is available for purchase or by subscription. See below.
Coloring invariants of knots and links are often intractable

Greg Kuperberg and Eric Samperton

Algebraic & Geometric Topology 21 (2021) 1479–1510

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.

PDF Access Denied

We have not been able to recognize your IP address as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

NP–hardness, \#P–hardness, knot invariants
Mathematical Subject Classification 2010
Primary: 20F10, 57M27, 68Q17
Received: 20 November 2019
Revised: 6 September 2020
Accepted: 22 September 2020
Published: 11 August 2021
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