Embeddability in R3 is NP-hard

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10384873" target="_blank" >RIV/00216208:11320/18:10384873 - isvavai.cz</a>
Výsledek na webu
<a href="https://epubs.siam.org/doi/10.1137/1.9781611975031.86" target="_blank" >https://epubs.siam.org/doi/10.1137/1.9781611975031.86</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611975031.86" target="_blank" >10.1137/1.9781611975031.86</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Embeddability in R3 is NP-hard
Popis výsledku v původním jazyce
We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ3 is NP-hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ3 like unknot or 3-sphere recognition which are in NP INTERSECTION co-NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.
Název v anglickém jazyce
Embeddability in R3 is NP-hard
Popis výsledku anglicky
We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ3 is NP-hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ3 like unknot or 3-sphere recognition which are in NP INTERSECTION co-NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

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í
2018
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 Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA18')
ISBN
978-1-61197-503-1
ISSN
—
e-ISSN
neuvedeno
Počet stran výsledku
14
Strana od-do
1316-1329
Název nakladatele
Neuveden
Místo vydání
Neuveden
Místo konání akce
New Orleans
Datum konání akce
7. 1. 2018
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)