Construção e Análise de Algoritmos - Lista de exercícios 4, Exercícios de Análise de Sistemas de Engenharia

Baixe Construção e Análise de Algoritmos - Lista de exercícios 4 e outras Exercícios em PDF para Análise de Sistemas de Engenharia, somente na Docsity! Universidade Federal do Ceará Centro de Ciências Departamento de Computação Mestrado e Doutorado em Ciência da Computação Construção e Análise de Algoritmos Lista de exerćıcios 4 1. (a) Explique informalmente o que significa um problema ser NP-Completo. Do ponto de vista prático, qual é a relevância de se determinar que um certo pro- blema é NP-Completo? (b) Para cada uma das afirmações abaixo, diga se ela e verdadeira, falsa, verdadeira se P 6=NP ou falsa se P 6=NP. Dê uma justificativa curta para cada resposta. (1) Não há problemas em P que são NP-Completos (2) Existe apenas algoritmo exponencial para o problema da parada (3) Existem problemas em P que estão em NP (4) Existem problemas em NP que não estão em P (5) Se A pode ser polinomialmente reduzido a B, e B é NP-Completo, então A é NP-Completo (6) Se A pode ser polinomialmente reduzido a B, e B ∈ P, então A ∈ P (7) O problema do Caixeiro Viajante é NP-Completo 2. Seja 0 < α < 1 um número qualquer. Seja (α)-CLIQUE o problema de decidir se, dado como entrada um grafo G, existe uma clique com mais de αn vértices, onde n é o número de vértices de G. Prove que (α)-CLIQUE é NP-Completo. 3. Dado um grafo G, uma coloração é uma atribuição de cores a seus vértices de forma que vértices adjacentes tenham cores diferentes. Seja 3CORES o problema de decidir se, dado um grafo G como entrada, G pode ser colorido com 3 cores. Mostre que 3CORES é NP-Completo. Figura 1. Use essas engrenagens na questão 1 4. Dizemos que um grafo G esta parcialmente rotulado se alguns de seus vértices possuem um número inteiro como rótulo. Dado um vértice rotulado v de G, seja r(v)