Propiedades estructurales de las jerarquías de conteo

  1. Teran Romero, Jacobo
Zuzendaria:
  1. José Luis Balcázar Navarro Zuzendaria

Defentsa unibertsitatea: Universitat Politècnica de Catalunya (UPC)

Defentsa urtea: 1988

Epaimahaia:
  1. Josep Díaz Cort Presidentea
  2. Llorenç Huguet Rotger Idazkaria
  3. Joaquim Gabarró Vallés Kidea
  4. Uwe Schoning Kidea
  5. Mario Rodríguez Artalejo Kidea

Mota: Tesia

Teseo: 20166 DIALNET

Laburpena

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.