加载中…
2012-11-27
Recognition of collapsible complexes is NP-complete
Martin Tancer
文献摘要
We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Franc'{e}s showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.
讨论
0讲解博客
生成讲解博客的中文版本
AI智能校验
生成AI智能校验的中文版本