Tesis doctoral de Montserrat Hermo Huguet
Se realiza un estudio exhaustivo de algunas clases de complejidad definidas a partir del modelo de maquina de turing determinista, con uso de funciones consejeras de tamaño subpolinomico. Concretamente: – se caracteriza la clase p/log. – se recupera la definicion de full-p/log, se caracteriza y se explica su estructura interna. – se extienden los resultados a las clases full-p/o(f(h)). – se obtienen resultados sobre el aprendizaje de expresiones regulares con circuitos que tienen complejidad baja. – aplicando un tipo de demostracion novedoso usado para caracterizar full-p/log, se demuestra la similitud existente entre varias definiciones ya conocidas en el ambito de la complejidad de secuencias infinitas. – se explica lo que ocurriria si los lenguajes de np o de exp fueran turing-reducibles a algun conjunto de densidad subpolinomica.
Datos académicos de la tesis doctoral «Nonuniform complexity classes with sub-linear advice functions.«
- Título de la tesis: Nonuniform complexity classes with sub-linear advice functions.
- Autor: Montserrat Hermo Huguet
- Universidad: País vasco/euskal herriko unibertsitatea
- Fecha de lectura de la tesis: 01/01/1996
Dirección y tribunal
- Director de la tesis
- José Luis Balcazar Navarro
- Tribunal
- Presidente del tribunal: Mario Rodríguez Artalejo
- Ricard Gavaldí Mestre (vocal)
- Jacobo Toran (vocal)
- Christoph Meinel (vocal)