Resumen de Propiedades estructurales de las jerarquías de conteo
Jacobo Teran Romero
SE ESTUDIAN TRES JERARQUIAS RELACIONADAS CON LA NOCION DE CONTAR: LA JERARQUIA DE CONTEO DE TIEMPO POLINOMICO, LA DE FUNCIONES DE CONTEO Y LA JERARQUIA DE CONTEO DE TIEMPO LOGARITMICO, INVESTIGAMOS LAS CONEXIONES ENTRE ESTAS JERARQUIAS Y ESTUDIAMOS SUS PROPIEDADES ESTRUCTURALES, OBTENIENDO RESULTADOS QUE RESUELVEN PROBLEMAS ABIERTOS RELATIVOS A CARACTERIZACION MEDIANTE ORACULOS, CIERRE POR OPERACIONES BOOLEANAS, CONJUNTOS BAJOS, REPRESENTACIONES SUCINTAS Y RELACIONES CON OTRAS CLASES DE COMPLEJIDAD.
