Nonuniform complexity classes with sub-linear advice functions
Montserrat Hermo · Dialnet (Universidad de la Rioja) · 1996
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 TAMANO 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.