Horario: 14 a 17 hs

Dr. Argimiro A. Arratia Quesada se doctoró en la Universidad de Wisconsin-Madison (EEUU) en 1996. En la actualidad es profesor del Departamento de Matemática de la Universidad Simón Bolivar de Venezuela. Sus temas de investigación están directamente relacionados con el curso que dictará y corresponde al estudio y caracterización de clases de complejidad a través de la lógica. Ha dictado varios seminarios y charlas sobre este tópico en diversas instituciones, como ser: los Dtos. de Computación de la Univesidad de Leicester y de la Universidad de Wales-Swansen; los Dto. de Matemáticas de las Universidades de Oxford, Illinois y Leeds;

La Teoría de la Complejidad Computacional pretende dar modelos de clasificación de los problemas resolubles en forma algorítmica según su dificultad de resolución en base a dos parámetros como son el tiempo y el espacio del modelo computacional. El objetivo de este curso es presentar al estudiante una infraestructura lógicos matemática, sobre la cual fundamentar los conceptos e ideas de la La Teoría de la Complejidad Computacional. Para ello se hará uso de la llamada Teoría Descriptiva de la Computabilidad, la cual clasifica un problema con respecto a cuan fácil sea definirlo en algún lenguaje formal, o lógico.

Lección 1. Elementos básicos de la Teoría de la Complejidad Computacional: máquina de Turing; clases de complejidad computacional y sus complementos; ejemplos de representantes en cada una de estas clases; planteamiento de las cuestiones fundamentales de la Teoría de la Complejidad Computacional. Elementos básicos de la Lógica Matemática: vocabularios, modelos, fórmulas; PO (lógica de Primer Orden); SO (lógica de Segundo Orden). El concepto de capturar las nociones computacionales por medio de expresiones de alguna lógica.

Teorema del día [Fagin, 1974]: La clase de problemas definibles en el fragmento existencial de SO es exactamente NP.

Lección 2. El concepto de equivalencia entre dos lógicas. Herramientas: Juegos de Ehrenfeucht-Fraisse. Aplicación: demostraré que PO está propiamente contenido en la clase computacional L. Definición de la clase monNP (NP monádico).

Teorema: Conectividad de gráfos no está en monNP, pero si está en co-monNP}.

Corolario: monNP ¹ co-monNP}.

Problema abierto: extender el resultado anterior a una demostración NP.¹ co-NP.

Lección 3. Extensiones de PO con cuantificadores generalizados: Describimos una manera de enriquecer el poder expresivo de PO para capturar las clases L hasta PSPACE. Definición de los cuantificadores DTC, TC, PS, HP y HEX, y su correspondencia con problemas computacionales conocidos. Teorema del día: sobre estructuras (finitas) ordenadas se tienen las siguientes igualdades:

[Immerman] PO + DTC = L y PO + TC = NL;

[Stewart] PO + PS = P y PO + HP = NP;

[Arratia-Stewart] PO + HEX = PSPACE;

y todas estas lógicas poseen una forma normal.

Definiré forma normal y mencionaré su significado computacional.

Teorema [Immerman]: PO + TC es cerrada bajo complemento.

Corolario: co-NL = NL.

Lección 4. Extensiones de PO con operadores inductivos: Definición de los operadores LFP

(menor punto fijo) y PFP (punto fijo parcial);

Teorema: sobre estructuras (finitas) ordenadas se tienen las siguientes igualdades:

[Immerman-Vardi]: PO + LFP = P; [Abiteboul-Vianu]: PO + PFP = PSPACE.

Complejidad Relacional. Variaciones de los operadores inductivos. Resultados que trasladan cuestiones fundamentales sobre complejidad computacional a cuestiones sobre equivalencia de lógicas. Por ejemplo:

Teorema [Abiteboul-Vianu]: sobre estructuras (finitas) arbitrarias, PO + LFP = PO + PFP si, y sólo si, P = PSPACE.

Lección 5. Lógica de Programas: Presentaré un modelo computacional a medio camino entre la máquina de Turing y un lenguaje lógico matemático, con una sintaxis más cercana a la de los lenguajes de programación usuales como Pascal o C. El modelo consiste en un conjunto de instrucciones de tipo WHILE ....... DO; IF ...... THEN ....... ELSE; y no determinismo dado por GUESS(). Demostraré la relación de este modelo con las lógicas estudiadas en la Lección 3. Definiré y demostraré una jerarquía de esta clase de programas con respecto a la profundidad de anidamiento de instrucciones del tipo WHILE .... DO; y una jerarquía similar cuando utilizamos la estructura de almacenamiento de tipo pila (stack). Una interpretación computacional de estos resultados es la siguiente: programas (como muchos que se utilizan en aplicaciones de la Inteligencia Artificial) que durante sus cómputos tienen la posibilidad de parar y correr un test (o subprograma) tienen mayor capacidad computacional que si no tuviesen este artificio. También, programas que utilizan la estructura de almacenamiento de datos de tipo pila tienen mayor capacidad computacional que aquellos que no la tienen. Y todo esto válido sobre estructuras finitas arbitrarias.

Nociones de algoritmos y complejidad computacional y conocimientos básicos de lógica.

Notas de los trabajos y resolucion
Resolucion (PostScript)