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 |