Propiedades estructurales de las jerarquías de conteo
- Teran Romero, Jacobo
- José Luis Balcázar Navarro Director/a
Universidad de defensa: Universitat Politècnica de Catalunya (UPC)
Año de defensa: 1988
- Josep Díaz Cort Presidente/a
- Llorenç Huguet Rotger Secretario/a
- Joaquim Gabarró Vallés Vocal
- Uwe Schoning Vocal
- Mario Rodríguez Artalejo Vocal
Tipo: Tesis
Resumen
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.