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

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

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

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.

PDF Access Denied

We have not been able to recognize your IP address 18.221.53.209 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-recommendation 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:

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)