MAC 828 Tópicos em Complexidade Computacional

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.