Complejidad algorítmica en homotopía racional
- Lechuga Pérez, Luis
- Aniceto Murillo Mas Director
Universidade de defensa: Universidad de Málaga
Ano de defensa: 1998
- Francisco Gómez Ruiz Presidente/a
- Antonio Angel Viruel Arbaizar Secretario/a
- José María Barja Pérez Vogal
- Antonio Gómez Tato Vogal
- Daniel Tanré Vogal
Tipo: Tese
Resumo
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.