MAC 722 Introdução à Teoria da Complexidade Computacional

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

• Aula 10 (1 de abril)
  • Problema da Parada: H = { M;x | M pára com entrada x}, onde M;x é uma codificação da máquina M e da entrada x.
  • Teorema H não é recursiva.
  • As linguagens que não são recursivas são chamadas indecidíveis.
  • Proposição As seguintes linguagens não são recursivas:
    • {M | M pára com qualquer entrada}
    • {M;x | existe y tal que M com entrada x para no estado h}
    • {M;x | M com entrada x "usa" todos os estados de M}
    • {M;x;y | M(x) = y}
  • Proposição L é recursiva se e somente se L e complemento(L) são recursivamente enumeráveis.
  • Proposição L é recursivamente enumerável se e somente se existe M tal que L = E(M)
  • Se M é uma máquina de Turing deterministica então L(M) denota a linguagem aceita por M. (Para máquina que para no estado "NÃO" para alguma entrada x temos que L(M) = vazio.)
  • Teorema (Rice) Seja L uma linguagem recursivamente enumerável não vazia. O seguinte problema é indecidível: dado M decidir se L(M) = L. (Notar que L é uma linguagem fixa.)
• Semana Santa (6 a 10 de abril) Não houve aula.
• Aula 11 (13 de abril)
  • Relações entre classes de complexidade. (Ver o Capítulo 7 do livro de Papadrimitriou.)
  • Teorema Existe uma função recursiva f dos naturais nos naturais tal que TIME(f(n)) = TIME(2^{f(n)}).
  • Definição de função própria de complexidade ou função fácil (deveriamos chamar este tipo de função de decente...).
• Aula 12 (15 de abril)
  • Primeira prova.
• 20 de abril Não houve aula.
• Aula 13 (22 de abril)
  • Comentários sobre a primeira prova
    • L pertence a TIME(n+1) implica L = vazio ou L = \sigma^*.
    • L = {M | L(M) é finita não é recursiva}. Usando a sugestão, a solução desta questão é semelhante a prova do Teorema de Rice.
    • L = {M | L(M) é infinita} não é revursivamente enumerável.
  • Recordação da definição de função fácil.
  • Lema Seja f:N -> N, uma função e H_f = { M;x | M aceita x em no máximo f(|x|) passos}. Então H_f pertence a TIME(f^3(n)).
• Aula 14 (27 de abril)
  • Seja f(n) >= n+2 uma função fácil. Definimos H_f={ M;x | M aceita x em no máximo f(|x|) passos}
  • Lema H_f pertence à TIME ((f(n))^3).
  • Lema H_f não pertence à TIME ((f([n/2])).
  • Teorema Seja f(n) >= n+2 uma função fácil. Então a classe TIME(f(n)) está propriamente contida na classe TIME((f(2n)^3).
  • Corolário P está propriamente contido em EXP.
  • Teorema Seja f(n) >= log n uma função fácil. Então a classe SPACE(f(n)) está propriamente contida na classe SPACE(f(n) log f(n)).
  • Teorema
    • SPACE(f(n)) \subseteq (está contido em) NSPACE(f(n))
    • TIME(f(n) \subseteq NTIME(f(n))
    • NTIME(f(n)) \subseteq SPACE(f(n))
    • NSPACE(f(n)) \subseteq \uniao_{i>0} TIME(i^{f(n) + log n})
  • Corolário SPACE(log n) \subseteq NSPACE(logn) \subseteq P \subseteq NP \supseteq PSPACE (=NPSPACE) \subseteq EXP. Observação: Na cadeia de inclusões acima sabe-se que SPACE(log n) está propriamente contida em PSPACE e que P está propriamente contida em EXP.
• Aula 15 (29 de abril)
  • Teorema (Savitch) O problema do st-caminho pertence a SPACE((log n)^2).
  • Corolário Se f(n) >= log n é uma função fácil, então NSPACE(f(n)) está contida em SPACE((f(n))^2).
  • Corolário PSPACE = NPSPACE.
  • Seja F uma função de strings em strings (\Sigma^* -> \Sigma^*). Então dizemos que uma máquina de Turing não deterministica computa F se para cada string x temos que
    • cada computação de M devolve F(x) (sucesso) ou termina no estado "NÃO" (fracasso);
    • existe pelo menos uma computação de M que devolve F(x).
  • Teorema (Immerman-Szelepcényi) Dado um grafo G e um vértice x, o número de vértices atingíveis a partir de x em G pode ser computado por uma máquina de Turing não-determinística em espaço log n.