NP-Hardness of Computing PL Geometric Category in Dimension 2
DOI10.1137/22m1523960zbMath1529.55003arXiv2204.13981OpenAlexW4386478101MaRDI QIDQ6077977
Michael Skotnica, Martin Tancer
Publication date: 27 September 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2204.13981
Lyusternik-Shnirel'man category of a space, topological complexity à la Farber, topological robotics (topological aspects) (55M30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc. (57Q10) Combinatorial aspects of simplicial complexes (05E45)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Topological complexity of motion planning
- Instabilities of robot motion
- Shellings from relative shellings, with an application to NP-completeness
- Some remarks on PL collapsible covers of 2-dimensional polyhedra
- Decompositions of two-dimensional simplicial complexes
- THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
- On the topological complexity of aspherical spaces
- Shellability is NP-complete
- Computational Complexity
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- Recognition of collapsible complexes is NP-complete
This page was built for publication: NP-Hardness of Computing PL Geometric Category in Dimension 2
