Some conditionally hard problems on links and 3-manifolds
Many decision problems in the theory of knots, links and 3-manifolds are known to be solvable. For example, the equivalence problem for links in the 3-sphere was solved by Haken, Hemion and Matveev. Following the work of many mathematicians, including the proof of the the Geometrisation Conjecture b...
Main Author: | |
---|---|
Format: | Journal article |
Published: |
Springer
2017
|
_version_ | 1797068946316197888 |
---|---|
author | Lackenby, M |
author_facet | Lackenby, M |
author_sort | Lackenby, M |
collection | OXFORD |
description | Many decision problems in the theory of knots, links and 3-manifolds are known to be solvable. For example, the equivalence problem for links in the 3-sphere was solved by Haken, Hemion and Matveev. Following the work of many mathematicians, including the proof of the the Geometrisation Conjecture by Perelman, the homeomorphism problem for compact orientable 3-manifolds is now solved. However, the complexity of these and other decision problems in low-dimensional topology remains poorly understood. The problem of deciding whether a knot is the unknot is a good test case. Haken was the first to find an algorithmic solution to this problem. It was shown to be in NP by Hass, Lagarias and Pippenger, and in co-NP by work of Agol, Kuperberg and the author. However, no polynomial-time algorithm has yet been found. |
first_indexed | 2024-03-06T22:17:20Z |
format | Journal article |
id | oxford-uuid:53d18d8a-6047-4284-82bd-6535f28a688f |
institution | University of Oxford |
last_indexed | 2024-03-06T22:17:20Z |
publishDate | 2017 |
publisher | Springer |
record_format | dspace |
spelling | oxford-uuid:53d18d8a-6047-4284-82bd-6535f28a688f2022-03-26T16:34:07ZSome conditionally hard problems on links and 3-manifoldsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:53d18d8a-6047-4284-82bd-6535f28a688fSymplectic Elements at OxfordSpringer2017Lackenby, MMany decision problems in the theory of knots, links and 3-manifolds are known to be solvable. For example, the equivalence problem for links in the 3-sphere was solved by Haken, Hemion and Matveev. Following the work of many mathematicians, including the proof of the the Geometrisation Conjecture by Perelman, the homeomorphism problem for compact orientable 3-manifolds is now solved. However, the complexity of these and other decision problems in low-dimensional topology remains poorly understood. The problem of deciding whether a knot is the unknot is a good test case. Haken was the first to find an algorithmic solution to this problem. It was shown to be in NP by Hass, Lagarias and Pippenger, and in co-NP by work of Agol, Kuperberg and the author. However, no polynomial-time algorithm has yet been found. |
spellingShingle | Lackenby, M Some conditionally hard problems on links and 3-manifolds |
title | Some conditionally hard problems on links and 3-manifolds |
title_full | Some conditionally hard problems on links and 3-manifolds |
title_fullStr | Some conditionally hard problems on links and 3-manifolds |
title_full_unstemmed | Some conditionally hard problems on links and 3-manifolds |
title_short | Some conditionally hard problems on links and 3-manifolds |
title_sort | some conditionally hard problems on links and 3 manifolds |
work_keys_str_mv | AT lackenbym someconditionallyhardproblemsonlinksand3manifolds |