Nonuniform complexity classes with sub-linear advice functions

  1. Hermo Huguet, Montserrat
Dirigida por:
  1. José Luis Balcázar Navarro Director/a

Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Año de defensa: 1996

Tribunal:
  1. Mario Rodríguez Artalejo Presidente/a
  2. Paqui Lucio Secretario/a
  3. Jacobo Toran Vocal
  4. Ricard Gavaldà Mestre Vocal
  5. Christoph Meinel Vocal

Tipo: Tesis

Teseo: 55397 DIALNET

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.