Parallel time and sequential reducibilities
- Autores: Carme Álvarez Faura
- Directores de la Tesis: Birgit Jenner (dir. tes.)
- Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 1994
- Idioma: inglés
- Tribunal Calificador de la Tesis: Joaquim Gabarró Vallés (presid.) , Ricard Gavaldà Mestre (secret.) , Felipe Cucker Farkas (voc.) , W. Allender Eric (voc.) , Klaus-Jorn Lange (voc.)
- Texto completo no disponible (Saber más ...)
- Resumen
LA TESIS ES UN ESTUDIO TEORICO DE LAS CLASES DE PROBLEMAS COMPUTACIONALES RESOLUBLES MUY RAPIDAMENTE MEDIANTE MODELOS PARALELOS DE CALCULO, EN PARTICULAR, SE ESTUDIA LA ESTRUCTURA FINA DE LAS CLASES NC Y AC DEFINIDAS POR PIPPENGER Y COOK.
LA PRIMERA PARTE DE LA TESIS ESTUDIA ALGUNOS PROBLEMAS CONCRETOS Y LOS CLASIFICA DE FORMA OPTIMA EN SUBCLASES DE NC; ASI, EL PROBLEMA DE LA PERTENENCIA A LENGUAJES DEFINIDOS POR REDES DE PETRI ES COMPLETO PARA LA CLASE TC, Y EL PROBLEMA DE LA EQUIVALENCIA DE TRAZAS ESTA EN NC2. PARA PODER CLASIFICAR OTRO TIPO DE PROBLEMAS, SE INTRODUCEN DESPUES NUEVAS CLASES DE FUNCIONES ASOCIADAS A PROBLEMAS DE CONTEO PARA MAQUINAS INDETERMINISTAS QUE FUNCIONAN EN ESPACIO LOGARITMICO. EN PARTICULAR, SE ESTUDIAN LAS PROPIDADES DE LAS CLASES L, SPAN-L Y OPT-L, SUS ANALOGIAS CON CLASES DE CONTEO EN TIEMPO POLINOMICO, Y SE IDENTIFICAN ALGUNOS PROBLEMAS COMPLETOS PARA CADA UNA DE ELLAS.
LA SEGUNDA PARTE UTILIZA LAS NOCIONES DE REDUCIBILIDAD EN TIEMPO POLILOGARITMICO Y REDUCIBILIDAD ADAPTIVA DEL ESPACIO LOGARITMICO PARA DAR TEOREMAS DE DESCOMPOSICION DE LAS JERARQUIAS AC Y NC. LOS RESULTADOS CIERRAN CASI COMPLETAMENTE PROBLEMAS ABIERTOS POR C. WILSON.
