Sobre el espacio cuasi-métrico de las funciones de complejidad de algoritmos.

Ponente(s): Diana Citlalli Castañeda Álvarez, José Margarito Hernández Morales Luz del Carmen Álvarez Marín

La teoría de los espacios cuasi-métricos está en desarrollo desde mediados del siglo pasado; en ella se encuentran resultados análogos a los resultados clásicos para espacios métricos y normados. En 1995 Schellekens introdujo el espacio de complejidad, conformado por el conjunto de funciones de complejidad de algoritmos y dotado de una función distancia (no simétrica) entre ellas, para dar un sustento métrico y topológico al análisis de complejidad de algoritmos. Posteriormente, Romaguera y Schellekens, presentan el espacio de complejidad dual, para dar una estructura matemática más robusta para el análisis de complejidad de programas y algoritmos. Presentaremos aquí el espacio de complejidad y de complejidad dual con sus respectivas cuasi-semimétricas y algunos resultados referentes a ellos.