Complejidad algorítmica en homotopía racional

• Autores: Luis Lechuga Pérez
• Directores de la Tesis: Aniceto Murillo Mas (dir. tes.)
• Lectura: En la Universidad de Málaga ( España ) en 1998
• Idioma: español
• Tribunal Calificador de la Tesis: Francisco Gómez Ruiz (presid.) , Antonio Angel Viruel Arbaizar (secret.) , José María Barja Pérez (voc.) , Antonio Gómez Tato (voc.) , Daniel Tanré (voc.)
• Texto completo no disponible (Saber más ...)
• 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.