ATC P2

_
Analise as seguintes afirmativas.
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema.
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma. A análise permite concluir que

A) apenas a afirmativa I está correta.
B) apenas a afirmativa II está correta.
C) apenas as afirmativas I e II estão corretas.
D) apenas as afirmativas I e III estão corretas.
E) todas as afirmativas estão corretas.
_

_
A análise de complexidade provê critérios para a classificação de problemas com base na computabilidade de suas soluções, utilizando-se a máquina de Turing como modelo referencial e possibilitando o agrupamento de problemas em classes. Nesse contexto, julgue os itens a seguir.

I - É possível demonstrar que P f NP e NP f P.
II - É possível demonstrar que se P . NP, então P 1 NP-Completo = i.
III Se um problema Q é NP-difícil e Q 0 NP, então Q é NP-completo.
IV - O problema da satisfatibilidade de uma fórmula booleana F (uma fórmula é satisfatível, se é verdadeira em algum modelo) foi provado ser NP-difícil e NP-Completo.
V - Encontrar o caminho mais curto entre dois vértices dados em um grafo de N vértices e M arestas não é um problema da classe P. Estão certos apenas os itens

A I, III e IV.
B II, III, e IV.
C III, IV e V.
D I, II, III, e IV.
E II, III, IV e V

O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação. Em linhas gerais, deseja-se saber se todo