Abstrakt
Simpliciální komplex je d-kolabovatelný, pokud může být zredukován na prázdný komplex postupným odstraňováním stěn dimenze nejvýše d-1 obsažených v jediné maximální stěně. Dokazujeme, že algoritmická otázka, zda je daný simpliciální komplex d-kolabovatelný je NP-úplná pro d alespoň 4 a polynomiálně řešitelná pro d nejvýše 2.
Jako pomocný krok dokazujeme, že d-kolabovatelnost je rozpoznatelná hladovým algoritmem pro d nejvýše 2, nicméně hladový algoritmus selhává pro vyšší hodnoty d. Simpliciální komplex je d-reprezentovatelný, pokud je nervem souboru konvexních množin v R^d.
Hlavní motivace studia d-kolabovatelných komplexů vychází z toho, že d-reprezentovatelné komplexy jsou d-kolabovatelné.