I. O problema discute as classes P e NP e os conceitos de problemas que podem ser resolvidos ou verificados de forma eficiente por um computador.
II. Problemas na classe P tem soluções que podem ser obtidas eficientemente, enquanto problemas na classe NP tem soluções que podem ser verificadas eficientemente, mesmo que não se conheça uma solução eficiente.
III. Problemas NP-completos são os mais difíceis da classe NP, uma vez que qualquer outro problema de NP pode ser transformado neles de forma eficiente.
I. O problema discute as classes P e NP e os conceitos de problemas que podem ser resolvidos ou verificados de forma eficiente por um computador.
II. Problemas na classe P tem soluções que podem ser obtidas eficientemente, enquanto problemas na classe NP tem soluções que podem ser verificadas eficientemente, mesmo que não se conheça uma solução eficiente.
III. Problemas NP-completos são os mais difíceis da classe NP, uma vez que qualquer outro problema de NP pode ser transformado neles de forma eficiente.
I. O problema discute as classes P e NP e os conceitos de problemas que podem ser resolvidos ou verificados de forma eficiente por um computador.
II. Problemas na classe P tem soluções que podem ser obtidas eficientemente, enquanto problemas na classe NP tem soluções que podem ser verificadas eficientemente, mesmo que não se conheça uma solução eficiente.
III. Problemas NP-completos são os mais difíceis da classe NP, uma vez que qualquer outro problema de NP pode ser transformado neles de forma eficiente.
I. O problema discute as classes P e NP e os conceitos de problemas que podem ser resolvidos ou verificados de forma eficiente por um computador.
II. Problemas na classe P tem soluções que podem ser obtidas eficientemente, enquanto problemas na classe NP tem soluções que podem ser verificadas eficientemente, mesmo que não se conheça uma solução eficiente.
III. Problemas NP-completos são os mais difíceis da classe NP, uma vez que qualquer outro problema de NP pode ser transformado neles de forma eficiente.
Baixe no formato PDF, TXT ou leia online no Scribd
Fazer download em pdf ou txt
Você está na página 1/ 3
Exercícios de 03/08/2023
Questão 1 [ENADE 2011]: 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 problema cuja solução pode ser eficientemente verificada por um computador, também pode ser eficientemente obtida por um computador. Por “eficientemente” ou “eficiente” significa “em tempo polinomial”.
A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de classe P. Os algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no tamanho das suas entradas.
Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo eficiente para resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la eficientemente, então o problema é dito estar em NP. Dessa forma, a classe de problemas para os quais suas soluções podem ser eficientemente verificadas é chamada de classe NP.
Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na classe NP pode ser eficientemente transformado nesse problema. Essa transformação eficiente envolve as entradas e saídas dos problemas.
Considerando as noções de complexidade computacional apresentadas acima, analise as afirmações que se seguem.
I. Existem problemas na classe P que não estão na classe NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na classe P.
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
É correto apenas o que se afirma em:
A) I.
B) IV.
C) I e III.
D) II e III.
E) II e IV.
Questão 2: Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, apresente como resposta a soma dos números das afirmações que estão corretas.
1. A descoberta do cientista não traz nenhuma informação nova quanto a igualdade ou diferença entre as classes P e NP, permanecendo, portanto, a hipótese aceita de que P≠NP 2. A descoberta do cientista implica P = NP. 4. A descoberta do cientista implica dizer que existe um algoritmo polinomial que resolve todos os problemas NP 8. Os dois problemas são problemas de decisão
Soma: ____________________________ Questão 3: Um cientista afirma ter encontrado uma redução polinomial de um problema NP (para o qual não se conhece solução eficiente) para um outro problema de P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, apresente como resposta a soma dos números das afirmações que estão corretas.
1. A descoberta do cientista não traz nenhuma informação nova quanto a igualdade ou diferença entre as classes P e NP, permanecendo, portanto, a hipótese aceita de que P≠NP
2. A descoberta do cientista implica P = NP.
4. A descoberta do cientista implica dizer que existe um algoritmo polinomial que resolve todos os problemas NP
8. Os dois problemas são problemas de decisão
Soma: ____________________________
Questão 4 [ENADE 2005 - adaptado]: 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 está contido em NP e vice-versa
II. É possível demonstrar que, se P é diferente de NP, não é possível um problema estar em P e também em NP-Completo III. Não é possível um problema estar em P e também em NP IV. Se um problema Q é NP-difícil e Q pertence a NP, então Q também é NP-completo V. O problema SAT é o primeiro problema que se demonstrou pertencer a NP VI. Encontrar o caminho mínimo entre dois vértices de um determinado grafo de N vértices e M arestas é um problema da classe P VII. Identificar se um determinado número inteiro existe em um vetor contendo N inteiros é um problema da classe P
Questão 5: Descreva um dos 21 problemas de Karp e apresente uma instância positiva e uma negativa para demonstrar o entendimento. Questão 6: Considerando 7 (sete) problemas computacionais, nomeados de A a G, suponha que todos os algoritmos existentes relacionados a esses problemas estão apresentados na tabela abaixo – nomeados P1 a P10. Com base exclusivamente nas informações fornecidas por essa tabela, associe cada um dos problemas à(s) sua(s) respectiva(s) classes (caso o problema não pertença a nenhuma classe, associe-o a Nenhuma).
As respostas para cada problema serão analisada individualmente. A associação do problema a uma classe incorreta (ou mais) anula a nota correspondente ao problema.
Algoritmo O que faz? Comple-
xidade no tempo P1 Resolve qualquer instância do problema de otimização A O(n3)
P2 Reduz o problema SAT (NP-Completo) ao problema de decisão F O(n)
P3 Verifica qualquer instância do problema de localização B Θ(n4)
P4 Resolve qualquer instância do problema de decisão D O(logn)
P5 Reduz o problema de localização B ao problema SAT (NP-Completo) Θ(n)
P6 Verifica qualquer instância do problema de decisão G O(1)
P7 Resolve qualquer instância do problema de decisão E Ω(n2)
P8 Reduz o problema SAT (NP-Completo) ao problema de decisão E O(nlogn)
P9 Reduz o problema SAT (NP-Completo) ao problema de localização B Θ(logn)
P10 Reduz o problema SAT (NP-Completo) ao problema de otimização A O(3n)
A ⦿ ⦿ P B ⦿ ⦿ NP C ⦿ ⦿ NP-completo D ⦿ ⦿ NP-difícil E ⦿ ⦿ Nenhuma F ⦿ G ⦿
