Recognition of Collapsible Complexes and its NP-completeness

Dato uno spazio topologico, è naturale chiedersi se esso sia contraibile; formalmente, si definisce il problema della contraibilità e se ne studia la decidibilità. Questa è una domanda a cui non è ovvio poter rispondere, poiché i concetti appena menzionati sono molto astratti. Ci si restringe quindi a una classe più ''concreta'' di spazi, i complessi simpliciali, e si definisce la collassabilità, una proprietà che implica la precedente, ma che può essere meglio studiata da un punto di vista combinatorico. Questa tesi si focalizza sullo studio della collassabilità di complessi simpliciali, analizzandone inoltre la complessità computazionale.