MAC 722 Introdução à Teoria da Complexidade Computacional

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

• Aula 24 (1 de junho)
  • Problema difíceis: uma linguagem L é difícil (hard) para uma classe $\mathcal{C}$ se para qualquer $L' \in \mathcal{C}$ $L'$ se reduz a $L$. (Note que não estamos exigindo que $L \in \mathcal{C}$
  • Problema FSAT
    Dado: um expressão Booleana $\phi$.
    Encontrar: uma atribuição que satisfaça $\phi$ ou resposnder "NÃO" caso não exista uma tal atribuição.
  • Problema da Coloração Mínima
    Dado: um grafo $G$.
    Encontrar: o menor número de cores necessárias para colorir os vértices de $G$.
  • Um problema de função é chamado NP-difícil (NP-hard) se a existência de uma máquina de Turing determinística que opera em tempo polinomial e resolve o problema implica que P=NP. Exemplos: FSAT, TSP, o Problema da Coloração Mínima e o Problema da Parada são NP-difíceis.
  • Proposição Se $L \subseteq \Sigma^*$ é NP-completo então $\overline{L} = \Sigma^*\setminus L$ é coNP-completo.
  • Proposição Se um problema coNP-completo está em NP, então coNP=NP.
  • Problema Primos
    Dado: um inteiro $n$.
    Pergunta: $n$ é primo?
  • Teorema (Pratt'75) Primos pertence a NP.
  • #SAT é o problema de encontrar o número de atribuições distintas que satisfazem uma dada expressão Booleana.
  • #HC é o problema de encontrar o número de circuitos Hamiltonianos distintos que possui um dado grafo.
  • (Problema de contagem) Dada uma linguagem $L$ em NP o problema de contagem associado à $L$ é o problema de dado $x \in \Sigma^*$ determinar o número de testemunha $y \in \Sigma^*$ que provam que $X$ está em $L$.
  • #P é a classe de todos os problemas de contagem associados a linguagens em NP.
  • #SAT e #HC são NP-difíceis.
  • (Redução parcimoniosa) Uma redução $R: \Sigma_1^* \rightarrow \Sigma_2^*$ de $L_1$ para $L_2$ é parcimoniosa se para todo $x \in \Sigma^*$ o número de testemunhas para a pertinência de $x$ em $L_1$ é igual ao número de testemunhas para a pertinência de $R(x)$ em $L_2$.
  • Definição Um problema de contagem $T$ associado a uma linguagem $L$ é #P-completo se o problema esta em #P e para todo problema de contagem associado a $L$ em NP temos que existe uma redução parcimoniosa que reduz $L'$ para $L$.
  • Teorema #SAT é #P-completo.
  • Teorema #HC é #P-completo.
  • Teorema (Valiant'79) O problema de contar o número de emparelhamentos perfeitos em um dado grafo bipartido é #P-completo. (Note que o problema de contagem deste teorema á o problema associado à uma linguagem em P!)
• Aula 25 (3 de junho)
  • Entrega da quinta lista de exercícios.
  • Máquina de Turing $M^L$ com oráculos (onde $L$ é uma linguagem); classes de linguagens decididas por Máquinas de Turing com oráculo (a classe P^SAT que contém tanto NP quanto coNP).
  • Teorema existe uma linguagem L para a qual P^L é igual a NP^L.
  • Teorema Existe uma linguagem L apara a qual P^L é distinta de NP^L.
  • Teorema IP = PSPACE.
  • Teorema Existe uma linguagem L para a qual IP^L é distinta de PSPACE^L.
  • Hierarquia Polinomial: as classe $\Delta_i$P, $\Sigma_i$P e $\Pi_i$P, para i=0,1,...
  • Teorema Uma linguagem L pertence a $\Sigma_i$P (i > 0) se e somente se existe R tal que \{ x;y | (x;y) \in R\} pertence a $\Pi_{i-1}$P e L = \{ x | existe y tal que (x,y) \in R\}. [R é uma relação polinomialmente balanceada, ou seja, |y| \leq |x|^k para todo (x,y) \in R.]
  • Corolário Uma linguagem L pertence a $\Pi_i$P (i > 0) se e somente se existe R tal que \{ x;y | (x;y) \in R\} pertence a $\Sigma_{i-1}$P e L = \{ x | existe y tal que (x,y) \in R\}. [R é uma relação polinomialmente balanceada, ou seja, |y| \leq |x|^k para todo (x,y) \in R.]
  • Corolário Uma linguagem L pertence a $\Sigma_i$P (i \geq 0) se e somente se L = \{ x | existe y_1 para todo y_2 existe y_3 ... Q y_i tal que (x,y_1,y_2,...,y_i) \in R\}, onde Q e um quantificador "existe" ou "para todo". [R é uma relação polinomialmente balanceada, ou seja, |y_i| \leq |x|^k para todo (x,y_1,...,y_i) \in R.]
  • Problema QBF (QSAT)
    Dado: uma expressão Booleana $\phi$ em CNF com variáveis x_1,x_2,...,x_n.
    Pergunta: a fórmula existe x_1 para todo x_2 existe x_3 ... Qx_n $\phi$ é satisfatível?
  • Teorema QBF é PSPACE-completo.
  • Problema QSAT_i
    Dado: uma expressão Booleana $\phi$ em CNF com variáveis particionadas em conjuntos X_1,X_2,...,X_n.
    Pergunta: a fórmula existe X_1 para todo X_2 existe X_3 ... QX_i $\phi$ é satisfatível?
  • Teorema QSAT_i é $\Signa_i$P--completo, i \geq 1.
  • Teorema PH \subseteq PSPACE
  • Teorema Se para algum $i \geq 1$, $\Sigma_i = \Pi_iP$, então para todo $j \geq i$, $\Sigma_jP = \Pi_jP = \Delta_jP = \Sigma_iP$.
  • Corolário Se P = NP ou NP = coNP então PH colapsa no seu primeiro nível.
  • Teorema Se existe algum problema PH-completo, então PH colapsa em algum nível $i$.
  • Observação Se P = PSPACE então existem problemas PH-completos (logo PH colapsa, pois PSPACE tem problemas completos.)
• Aula 26 (8 de junho)
• Aula 27 (10 de junho) (Jogo do Brasil)
• Aula 28 (15 de junho) (Seminário do Juliano)
• Aula 29 (17 de junho) (Seminário do Carlos)
• Aula 30 (22 de junho) (Seminário do Marcelo)
• Aula 31 (24 de junho) (Seminário do Marcio)
• Aula 32 (29 de junho) (Seminário da Liliane)