MAC 828 T�picos em Complexidade Computacional
Hor�rio: segundas-feiras das 14 �s 16hs e quartas-feiras das 16 �s 18hs .
Local: sala 267 do bloco A e sala 6 do bloco B.
Conte�do das Aulas durante o m�s de outubro
- Aula 15 (5 de outubro)
Marcelo Finger
O Teorema de Fagin: Parte I (Preliminares)
- Cla�sulas de Horn.
- Teorema O problema de decidir se uma clausula de
Horn � satisfat�vel esta em P.
- L�gica de 1a. ordem: sintaxe, modelos (exemplos: modelos de
Teoria dos N�meros e modelos de Teoria dos Grafos); Cla�sulas de
Horn; O problema \phi-GRAPHS.
- Teorema Para toda expressao \pri em \Sigma_G, o
problema \phi-GRAPHS esta em P.
- Forma Normal Prenex.
- Aula 16 (7 de outubro)
Marcelo Finger
O Teorema de Fagin: Parte II (Preliminares + parte f�cil do teorema)
- L�gica de 2a. ordem. Express�o em l�gica de 2a. ordem que
cap�tura a exist�ncia de um s-t-caminho em um grafo.
- Teorema. Seja \exits P \phi uma f�rmula
existencial em l�gica de 2a. ordem. Ent�o o problema (\exits P
\phi)-GRAPHS est� em NP.
- Teorema de Fagin. NP � precisamente a classe de
todas as linguagens redut�veis a alguma propriedade em grafos
express�vel em l�gica existencial de 2a. ordem. (Parte I)
- Aula 17 (14 de outubro)
Liliane
- Problema de otimiza��o. Algoritmos polinomiais de
\epsilon-Aproxima��o. Inaproximibilidade do Problema de
Cobertura de V�rtices e do Problema do Caixeiro Viajante.
- PTAS (Polynomial-Time Approximation Scheme) e
FPTAS (Fully Polynomial-Time Approximation Scheme).
- L-redu��es.
- Aula 18 (19 de outubro)
Liliane
- L-redu�oes (continua��o).
- Proposi��o (Transitividade de L-redu��es) Se (R,S) �
uma L-redu��o do problema A para o problema B e (R',S') � uma
L-redu��o do problema B para o problema C, ent�o a
composi��o (R.R',S'.S) � uma L-redu��o de A para C.
- Proposi��o Se existe uma L-redu��o (R,S) de A para B
com constantes \alpha e \beta, e existe um algoritmo polinomial
de \epsilon-aproxima��o para B, ent�o existe um algoritmo
polinomial polinomial de ((\alpha \beta
\epsilon)/(1-\epsilon))-aproxima��o para A.
- Corol�rio Se existe uma L-redu��o de A para B e
existe um (F)PTAS para Bm, ent�o existe um (F)PTAS para A.
- A classe MAXSNP.
- Aula 19 (21 de outubro)
Marcelo Finger
O Teorema de Fagin: Parte III (ep�logo)
- Teorema de Fagin. NP � precisamente a classe de
todas as linguagens redut�veis a alguma propriedade em grafos
express�vel em l�gica existencial de 2a. ordem.
- Aula 20 (26 de outubro)
Marcio
- Complexidade de informa��o: complexidade, c�digo de
Kolmogorov $K_T(x)$.
- Lema Existe uma constante $c_T$ tal que $K_T(x) \leq
|x| + c_T$.
- Invariance Theorem Sejam $T$ e $S$ duas m�quinas de
Turing universais `padronizadas'. Ent�o existe uma contante
$c_{TS}$ tal que para cada palavra $x$ temos que |K_T(x) -
K_S(x)| \leq c_{TS}$.
- Aula 21 (28 de setembro)
Marcio
- Teorema A fun��o $K(x)$ � n�o-recursiva.
- Teorema Para cada distribui��o de probabilidades
comput�vel existe um algoritmocomputando um c�digo de Kolmogorov
$f(x)$ para cada palvra $x$ tal que o valor esperado de |f(x)| -
K(x) � finito.
MAC 828 - Conte�do das aulas.
Last modified: Tue Nov 17 09:53:12 EDT 1998