Complejidad algorítmica en homotopía racional
- Lechuga Pérez, Luis
- Aniceto Murillo Mas Doktorvater/Doktormutter
Universität der Verteidigung: Universidad de Málaga
Jahr der Verteidigung: 1998
- Francisco Gómez Ruiz Präsident/in
- Antonio Angel Viruel Arbaizar Sekretär/in
- José María Barja Pérez Vocal
- Antonio Gómez Tato Vocal
- Daniel Tanré Vocal
Art: Dissertation
Zusammenfassung
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.