The Unbearable Hardness of Unknotting

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403723" target="_blank" >RIV/00216208:11320/19:10403723 - isvavai.cz</a>
Výsledek na webu
<a href="https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10453" target="_blank" >https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10453</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.49" target="_blank" >10.4230/LIPIcs.SoCG.2019.49</a>

Jazyk výsledku
angličtina
Název v původním jazyce
The Unbearable Hardness of Unknotting
Popis výsledku v původním jazyce
We prove that deciding if a diagram of the unknot can be untangled using at most k Reidemeister 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).
Název v anglickém jazyce
The Unbearable Hardness of Unknotting
Popis výsledku anglicky
We prove that deciding if a diagram of the unknot can be untangled using at most k Reidemeister 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).

Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2019
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019)
ISBN
978-3-95977-104-7
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
19
Strana od-do
1-19
Název nakladatele
Leibniz International Proceedings in Informatics (LIPIcs)
Místo vydání
Dagstuhl
Místo konání akce
Portland
Datum konání akce
18. 6. 2019
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)