Cotas inferiores para problemas decisionales en teoría de complejidad algebraica

Abstract

LA TESIS VERSA SOBRE LA OBTENCION DE COTAS INFERIORES EN TEORIA DE COMPLEJIDAD ALGEBRAICA, UTILIZANDO MODELOS DE COMPUTACION DECISIONALES SE HAN MOSTRADO COTAS INFERIORES DEL TIPO (N) PARA PROBLEMAS DE OPTIMIZACION FINITA SOBRE EL CONJUNTO DE LOS NUMEROS REALES. SE HAN OBTENIDO COTAS INFERIORES PARA LA COMPLEJIDAD NO ESCALAR QUE PROPORCIONAN COTAS INFERIORES DEL TIPO (NLOG2N) PARA CIERTOS PROBLEMAS DE PROXIMIDAD. SE HA ANALIZADO UN MODELO DE COMPUTACION UNIFORME SOBRE LOS REALES: LAS MAQUINAS DE BLUM, SHUB Y SMALE, MOSTRANDO UNA INTERPRETACION GEOMETRICA DE LA CLASE DE LENGUAJES RECONOCIDOS POR MAQUINAS CUYA FUNCION DE TIEMPO ESTA DEFINIDA. SE HAN DEMOSTRADO TEOREMAS DE JERARQUIA DE TIEMPO DENTRO DE DICHA CLASE. SE HA ESTABLECIDO UN MODELO DE COMPUTACION UNIFORME PARA LA COMPUTACION PARALELA SOBRE LOS REALES, OBTENIENDOSE COTAS INFERIORES TOPOLOGICAS PARA ESTE MODELO. FINALMENTE SE HA ESTUDIADO LA INFLUENCIA DE LA TEORIA DE COMPLEJIDAD ALGEBRAICA EN TOPOLOGIA Y TEORIA DE LA APROXIMACION.