Tesis doctoral de Carme Alvarez Faura
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.
Datos académicos de la tesis doctoral «Parallel time and sequential reducibilities«
- Título de la tesis: Parallel time and sequential reducibilities
- Autor: Carme Alvarez Faura
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 01/01/1994
Dirección y tribunal
- Director de la tesis
- Birgit Jenner
- Tribunal
- Presidente del tribunal: Joaquim Gabarró Vallés
- W. Allender Eric (vocal)
- Felipe Cucker Farkas (vocal)
- Klaus-jorn Lange (vocal)