The unbearable hardness of unknotting
| Autor: | Yo'av Rieck, Arnaud de Mesmay, Martin Tancer, Eric Sedgwick |
|---|---|
| Přispěvatelé: | GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Centre National de la Recherche Scientifique (CNRS), University of Arkansas [Fayetteville], School of Computing [DePaul] (SOC), DePaul University [Chicago], Department of Applied Mathematics [Prague] (KAM), Charles University [Prague] (CU), de Mesmay, Arnaud |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
000 Computer science
knowledge general works General Mathematics 010102 general mathematics Geometric Topology (math.GT) 01 natural sciences Mathematics::Geometric Topology Combinatorics symbols.namesake Mathematics - Geometric Topology Euler characteristic [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] Computer Science 0103 physical sciences symbols FOS: Mathematics 010307 mathematical physics 0101 mathematics Variety (universal algebra) Link (knot theory) Unknot Topology (chemistry) ComputingMilieux_MISCELLANEOUS Mathematics [MATH.MATH-GT] Mathematics [math]/Geometric Topology [math.GT] |
| Zdroj: | SoCG 2019-35th International Symposium on Computational Geometry SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, United States |
| Popis: | We prove that deciding if a diagram of the unknot can be untangled using at most $k$ Riedemeister moves (where $k$ is part of the input) is NP-hard. We also prove that several natural questions regarding links in the $3$-sphere are NP-hard, including detecting whether a link contains a trivial sublink with $n$ components, computing the unlinking number of a link, and computing a variety of link invariants related to four-dimensional topology (such as the $4$-ball Euler characteristic, the slicing number, and the $4$-dimensional clasp number). 36 pages, 21 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|