Nerves of Good Covers Are Algorithmically Unrecognizable

DOI10.1137/120891204zbMath1277.05175arXiv1205.6082MaRDI QIDQ2862208

Martin Tancer, Dmitry Tonkonog

Publication date: 14 November 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.6082

zbMATH Keywords

good cover; nerve; intersection pattern; algorithmic undecidability; piecewise-linear embedding

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05E45: Combinatorial aspects of simplicial complexes

57Q40: Regular neighborhoods in PL-topology