Complejidad algorítmica en homotopía racional
- Lechuga Pérez, Luis
- Aniceto Murillo Mas Director
Defence university: Universidad de Málaga
Year of defence: 1998
- Francisco Gómez Ruiz Chair
- Antonio Angel Viruel Arbaizar Secretary
- José María Barja Pérez Committee member
- Antonio Gómez Tato Committee member
- Daniel Tanré Committee member
Type: Thesis
Abstract
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.