Tesis doctoral de Luis Lechuga Perez
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.
Datos académicos de la tesis doctoral «Complejidad algoritmica en homotopia racional.«
- Título de la tesis: Complejidad algoritmica en homotopia racional.
- Autor: Luis Lechuga Perez
- Universidad: Málaga
- Fecha de lectura de la tesis: 01/01/1998
Dirección y tribunal
- Director de la tesis
- Aniceto Murillo Mas
- Tribunal
- Presidente del tribunal: Francisco Gomez Ruiz
- Antonio Gomez Tato (vocal)
- Barja Perez José María (vocal)
- Daniel Tanré (vocal)