Embeddability in R-3 is NP-hard

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10421443" target="_blank" >RIV/00216208:11320/20:10421443 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Qd6bGqbXRj" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Qd6bGqbXRj</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3396593" target="_blank" >10.1145/3396593</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Embeddability in R-3 is NP-hard

Popis výsledku v původním jazyce

We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R-3 is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S-3 filling is NP-hard. The former stands in contrast with the lower-dimensional cases, which can be solved in linear time, and the latter with a variety of computational problems in 3-manifold topology, for example, unknot or 3-sphere recognition, which are in NP boolean AND co-NP. (Membership of the latter problem in co-NP assumes the Generalized Riemann Hypotheses.) 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 of manifolds with boundary tori.

Název v anglickém jazyce

Embeddability in R-3 is NP-hard

Popis výsledku anglicky

We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R-3 is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S-3 filling is NP-hard. The former stands in contrast with the lower-dimensional cases, which can be solved in linear time, and the latter with a variety of computational problems in 3-manifold topology, for example, unknot or 3-sphere recognition, which are in NP boolean AND co-NP. (Membership of the latter problem in co-NP assumes the Generalized Riemann Hypotheses.) 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 of manifolds with boundary tori.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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í

2020

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 periodika

Journal of the ACM

ISSN

0004-5411

e-ISSN

—

Svazek periodika

67

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

20

Kód UT WoS článku

000582595200002

EID výsledku v databázi Scopus

2-s2.0-85090119393