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.