Limitaciones del método de Ehrenfeucht y Fraïssé en la complejidad descriptiva

SEMINAR

Speaker:
Dr. Joerg Flum
Dpt. Mathematical Logic
Albert-Ludwigs-Universität Freiburg (Alemania)

Title: Limitaciones del método de Ehrenfeucht y Fraïssé en la complejidad descriptiva

Abstract:

Con mucho provecho se ha utilizado el método de Ehrenfeucht y Fraïssé en la lógica de primer orden y en otras lógicas relevantes en la complejidad descriptiva. Sin embargo, con este método no se ha obtenido progreso alguno en la solución de problemas centrales como son, por ejemplo, los problemas P = NP y NP = coNP. Veremos que para este tipo de problemas ya es difícil obtener los tableros para aplicar el juego de Ehrenfeucht y Fraïssé.

Information:

Date: Thursday, 30-04-2015
Time: 10:00h.
Place: Seminar room H1.50 (First floor, Módulo H, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla)
Language: Spanish

Organized by: Research Group on Natural Computing