Link Crossing Number is NP-hard
| Autor: | Eric Sedgwick, Marcus Schaefer, Arnaud de Mesmay |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, School of Computing [DePaul] (SOC), DePaul University [Chicago] |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Computational Geometry (cs.CG) FOS: Computer and information sciences Algebra and Number Theory Computational complexity theory Crossing number (knot theory) 010102 general mathematics Geometric Topology (math.GT) [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Mathematics - Geometric Topology [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] 0103 physical sciences FOS: Mathematics Computer Science - Computational Geometry 010307 mathematical physics 0101 mathematics ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Journal of Knot Theory and Its Ramifications Journal of Knot Theory and Its Ramifications, World Scientific Publishing, 2020, 29 (06), pp.2050043. ⟨10.1142/S0218216520500431⟩ |
| ISSN: | 0218-2165 |
| Popis: | We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|