Propiedades estructurales de las jerarquías de conteo

  1. Teran Romero, Jacobo
Dirigida por:
  1. José Luis Balcázar Navarro Director/a

Universidad de defensa: Universitat Politècnica de Catalunya (UPC)

Año de defensa: 1988

Tribunal:
  1. Josep Díaz Cort Presidente/a
  2. Llorenç Huguet Rotger Secretario/a
  3. Joaquim Gabarró Vallés Vocal
  4. Uwe Schoning Vocal
  5. Mario Rodríguez Artalejo Vocal

Tipo: Tesis

Teseo: 20166 DIALNET

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.