Abstrakt
Simpliciální komplex je d-kolabovatelný, pokud může být redukován na prázdný komplex postupným odebíráním (kolabováním) stěny dimenze nejvýše d-1, která je obsažena v jediné maximální stěně. Dokuzejeme, že algoritmická otázka, zda je daný simpliciální komplex d-kolabovatelný, je NP-úplná pro d alespoň 4, zatímco je polynomiální pro d nejvýše 2.
Jako mezikrok našeho důkazu, ukazujeme, že d-kolabovatelnost může být rozpoznána hladovým algoritmem pro d {= 2, nicméně hladový algoritmus nefunguje pro d }=3.