1. Sejam P₁, P₂ e P₃ três problemas tais que P₁ a_n P₂ a_n³logn P₃ (i.e., P₁ é redutível a P₂ em tempo linear e P₂ a P₃ em tempo n³ log n). Assuma a hipótese de que P₁ é W(n log n). Assuma também que você conhece um algoritmo O (n³) para resolver P₃. Discuta as afirmações abaixo.
   1. O que você pode dizer sobre a complexidade de resolução de P₂ ? Qual a complexidade do melhor algoritmo que você conhece para P₂ ?
   2. Todo algoritmo que resolve P₂ tem que gastar pelo menos tempo quadrático (P₂ é W(n²)).
   3. W(n log n) é um limite inferior para a complexidade de P₃.
   4. Todo algoritmo que resolve P₁ pode ser usado para resolver P₂.
   5. Todo algoritmo que resolve P₃ pode ser usado para resolver P₂.
   6. P₂ pode ser resolvido no pior caso em tempo O(n log n).
   
   
2. Defina as classes de problemas P, NP e NP-completo Relacione estas classes e dê um exemplo de problema para cada classe.
   
   
3. Seja P o conjunto dos problemas para os quais existem algoritmos determinísticos polinomias para a sua resolução. Seja NP o conjunto dos problemas para os quais existem algoritmos não-determinísticos polinomias para a sua resolução. Naturalmente P está contido em NP. Considere os problemas P₁ Î P e P₂ Î NP-completo. Indique se cada afirmação abaixo é verdadeira, falsa ou se não se sabe.
   1. Conhece-se uma redução de P₁ para P₂ que toma tempo polinomial (O(n^k)).
   2. Se existe um algoritmo determinístico polinomial para a resolução de P₂ então podemos afirmar que P₁ Î NP-completo assim como P₂ Î P.
   3. P₂ é pelo menos tão difícil quanto 3-SAT.
   4. 3-SAT é pelo menos tão difícil quanto P₂.
   5. Existe uma redução de P₂ para P₁ que toma tempo polinomial.
   
   
   
   
   
   
   
   
4. Dado que você conhece um algoritmo determinístico polinomial para a resolução do problema (CMC) abaixo, USE ESTE CONHECIMENTO para provar que você também conhece um algoritmo determinístico polinomial para a resolução do problema (VMC) apresentado em seguida.
   
   (CMC) Dado um grafo orientado G=(V,A) com comprimentos positivos associados aos arcos (i,j) Î A, dois vértices i,j Î V e uma constante K. Pergunta-se se existe uma caminho do vértice i ao vértice j que possua comprimento menor ou igual à K.
   
   (VMC) Dado um grafo orientado G=(V,A), com comprimentos positivos associados aos arcos (i,j) Î A, e uma constante K. Pergunta-se se existe um par de vértices (i,j) para o qual exista um caminho de i a j e de j a i que tenha comprimento menor ou igual à K.
   
   
5. Sabe-se que o problema (MC), abaixo, pertence a NP-completo. Use este conhecimento para provar que (MS) também pertence a NP-completo.
   
   Clique-Máximo (MC) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um clique (isto é um sub-grafo completo) de cardinalidade maior ou igual à K.
   
   Estável-Máximo (MS) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um conjunto de vértices independentes (isto é, um conjunto de vértices onde não existe aresta entre nenhum par do conjunto) de cardinalidade maior ou igual à K.
   
   (Dica: Siga os passos para provar que um problema é NP-completo. A redução pedida aqui é muito, mas muito simples. Leia com cuidado e desenhe exemplos dos problemas).
   
   
6. Considere o problema abaixo:
   
   (MS): Dados um conjunto de máquinas M={ m₁, m₂, ..., m_p} e um conjunto de tarefas T={ t₁, t₂, ...,t_q} cada uma com uma duração d_i, i=1,...,q associada e uma constante K. Considerando-se que as tarefas podem ser atribuídas à qualquer máquina indistintamente. Pergunta-se se existe uma atribuição das tarefas às p máquinas tal que o instante em que a última tarefa é terminada é menor ou igual que K (Isto é, a duração total é inferior ou igual a K).
   
   Dado que este problema pertence a NP-completo responda:
   1. Quando temos um algoritmo polinomial determinístico para resolvê-lo ?
   2. Proponha um algoritmo para resolver este problema em tempo polinomial.
   3. Em que casos a solução obtida pelo seu algoritmo é correta ?
   4. Descreva um algoritmo que encontre sempre a resposta correta para este problema.

This document was translated from L^AT_EX by H^EV^EA.