Tesis doctoral de Elvira Mayordomo Camara
La tesis presenta extensiones y nuevas aplicaciones de la teoria de la medida con recursos acotados introducida por jack lutz. Esta teoria redefine conceptos clasicos de medida y categoria y los reformula de manera que puedan aplicarse a clases de complejidad de problemas computacionales. en el capitulo 2, se extienden las definiciones de lutz y se obtiene una nocion valida de medida dentro de la clase de problemas resolubles en espacio polinomico (la definicion de lutz solo tenia sentido para clases en tiempo exponencial o mayores). Con esta definicion, se demuestra que los conjuntos auto-reducibles son un conjunto de medida o en espacio polinomico. En el capitulo 3, se aplican tecnicas similares para demostrar que los conjuntos bi-inmunes tienen medida 1 en tiempo exponencial, extendiendo resultados anteriores puramente existenciales. En el capitulo 4 se utiliza el concepto de medida y estocasticidad debil para demostrar que todo conjunto «hard» para tiempo exponencial bajo un tipo especifico de reducibilidad es denso; el resultado obtenido es el mas fuerte conocido en la actualidad. el capitulo 5 estudia las consecuencias de la hipotesis que la clase np no tiene medida o en tiempo exponencial, derivando numerosas consecuencias estructurales. finalmente, el capitulo 6 relaciona nociones como la » -randomness» con la teoria de la medida.
Datos académicos de la tesis doctoral «Contributions to the study of resource-bounded measure«
- Título de la tesis: Contributions to the study of resource-bounded measure
- Autor: Elvira Mayordomo Camara
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 01/01/1994
Dirección y tribunal
- Director de la tesis
- José Luis Balcazar Navarro
- Tribunal
- Presidente del tribunal: Jacobo Toran Romero
- Mario Rodríguez Artalejo (vocal)
- V. Book Ronald (vocal)
- Marta Sanz (vocal)