Resumen de Nonuniform complexity classes with sub-linear advice functions

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.