MAC 828 Tópicos em Complexidade Computacional

Conteúdo das Aulas durante o mês de setembro

• Aula 8 (4 de setembro) Glauber
  • Teorema. QFB é PSPACE-completo (a ser continuado)
• Aula 9 (14 de setembro) Glauber
  • Teorema. QFB é PSPACE-completo (epílogo)
• Aula 10 (18 de setembro) Carlos Eduardo
  • Classes de complexidade probabilísticos: RP, coRP e ZPP.
  • Máquinas de Turing padronizadas. Máquina de Turing (não-determinística) do tipo Monte Carlo. A classe de linguagens que admitem uma Maquina de Turing polinomial do tipo Monte Monte Carlos --- a classe RP. Classes de complexidades sintáticas e semânticas (as classes RP e coRP são semânticas---P e NP são sintáticas).
  • ZPP = RP \cap coRP: algoritmos do tipo Las Vegas (composição dois algoritmos do tipo Monte Carlo).
• Aula 11 (21 de setembro) Carlos Eduardo
  • A classe de complexidade PP: Máquinas de Turing polinomias não-determinísticas que decidem por maioria simples. (A classe PP é sintática e não semântica.)
  • Teorema NP \subseteq PP. (Logo, coNP \subseteq PP.)
  • RP \subseteq RPP \subseteq PP. PP = coPP (PP é simetrica). BPP = coBPP (BPP é simétrica).
  • Fontes aleatórias. Fontes levemente aleatórias.
• Aula 12 (23 de setembro) Estela
  • Hierarquia Polinomial. As classe \Delta_i P, \Sigma_i P e \Pi_i P.
  • Teorema. L pertence a \Sigma_i P se e somente se existe uma relação R tal que L = \{ x | para todo y, |y| < |x|^k, vale que (x,y) \in R\} e \{x;y | (x,y) \in R\} é uma linguagem em \Pi_{i-1}P.
• Aula 13 (28 de setembro) Estela
  • Teorema. L pertence a \Pi_i P se e somente se existe uma relação R tal que L = \{ x;y | para todo y, |y| < |x|^k, vale que (x,y) \in R\} e \{x;y | (x,y) \in R\} é uma linguagem em \Sigma_{i-1} P.
  • Teorema. L pertence a \Sigma_i P se e somente se existe uma relação R (i+1)-ária tal que L = \{ x; existe y_1 para todo y_2 existe y_3 ... Qy_i (x,y_1,y_2,...,y_i) \in R\} e |y_i| < |x|^k, para todo i sempre que (x,y_1,...,y_i) \in R.
  • Teorema. Se \Sigma_i P = \Pi_i P para algum (i >= 1) então \Sigma_j P = \Pi_j P = \Delta_j P = \Sigma_i P para todo j > i (i.e. a hierarquia polinomial colapsa no nível i).
• Aula 14 (30 de setembro) Estela
  • Teorema. BPP \in \Sigma_2 P.
  • Teorema. Se SAT admite um circuito polinomial então a hierarquia polinomial colapsa no segundo nível.