Nonuniform complexity classes with sub-linear advice functions
- José Luis Balcázar Navarro Director/a
Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea
Año de defensa: 1996
- Mario Rodríguez Artalejo Presidente/a
- Paqui Lucio Secretario/a
- Jacobo Toran Vocal
- Ricard Gavaldà Mestre Vocal
- Christoph Meinel Vocal
Tipo: Tesis
Resumen
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.