Complejidad algorítmica en homotopía racional

Resumen

El objetivo central de la tesis es demostrar que la mayoría de los invariantes asociados a espacios topológicos racionales son NP-difíciles de calcular, Para evaluar la complejidad algorítmica de estos invariantes se los relacionan con problemas clásicos en complejidad algorítmica cuya dificultad es ya conocida como el k-coloreado de grafos. Se demuestra por tanto que el cálculo de la Categoría de Lusternik-Schinirelmann, el rango de la cohomología racional o el cálculo de los números de Betti son problemas NP-difíciles de solucionar. No obstante, y basado en un resultado puramente topológico cual es el cálculo de la clase fundamental de cohomología se dan algoritmos para, en determinados casos, resolver el problema del número cromático.