Nonuniform complexity classes with sub-linear advice functions

• Autores: Montserrat Hermo Huguet
• Directores de la Tesis: José Luis Balcázar Navarro (dir. tes.)
• Lectura: En la Universidad del País Vasco - Euskal Herriko Unibertsitatea ( España ) en 1996
• Idioma: inglés
• Tribunal Calificador de la Tesis: Mario Rodríguez Artalejo (presid.) , Paqui Lucio (secret.) , Jacobo Toran (voc.) , Ricard Gavaldà Mestre (voc.) , Christoph Meinel (voc.)
• Texto completo no disponible (Saber más ...)
• 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.