Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — Gama Consult 2024

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg202007
Banca
Gama Consult
Órgão
Câmara de Alto Paraíso - RO
Ano
2024
Nível
Superior
Cargo
Gestor de Tecnologia da Informação
Na computação, várias disciplinas aplicam conceitos matemáticos avançados para resolver problemas complexos. Uma dessas disciplinas é a Teoria da Complexidade Computacional, que estuda a eficiência dos algoritmos e a dificuldade dos problemas. Considere os conceitos de classes de complexidade, problemas NP-completos e algoritmos aproximados. Qual das seguintes afirmações sobre essas disciplinas é a mais correta?
  1. ATodo problema na classe NP pode ser resolvido em tempo polinomial por um algoritmo determinístico.
  2. BUm problema NP-completo é aquele para o qual não existe nenhum algoritmo de aproximação eficiente conhecido.
  3. CSe um problema NP-completo puder ser resolvido em tempo polinomial, todos os problemas em NP também poderão ser resolvidos em tempo polinomial.
  4. DAlgoritmos aproximados garantem sempre a solução exata de problemas NP-difíceis em tempo polinomial.
Revelar gabarito e comentário

GabaritoC — Se um problema NP-completo puder ser resolvido em tempo polinomial, todos os problemas em NP também poderão ser resolvidos em tempo polinomial.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Teoria da Complexidade Computacional: NP-completude

Gabarito: letra C. A definição de NP-completude implica que, se um problema NP-completo puder ser resolvido em tempo polinomial por um algoritmo determinístico, então todos os problemas em NP também poderão ser resolvidos em tempo polinomial, pois qualquer problema NP pode ser reduzido polinomialmente a um problema NP-completo. Esse é o cerne da questão P vs NP.

Alternativa A — ❌ Incorreta

Afirma que todo problema em NP pode ser resolvido deterministicamente em tempo polinomial, o que seria a definição da classe P, não de NP. NP contém problemas que podem ser verificados em tempo polinomial, mas não necessariamente resolvidos em tempo polinomial (P ⊆ NP, mas não se sabe se a inclusão é própria).

Alternativa B — ❌ Incorreta

Afirma que problemas NP-completos não possuem algoritmos de aproximação eficientes conhecidos. Na verdade, muitos problemas NP-completos possuem algoritmos de aproximação com razões constantes (ex.: cobertura de vértices tem um algoritmo de 2-aproximação; caixeiro viajante métrico tem um algoritmo de 2-aproximação). A existência de algoritmos de aproximação não contradiz a NP-completude.

Alternativa C — ✅ Correta ⟵ GABARITO

Conforme a definição de NP-completude, um problema é NP-completo se está em NP e todo problema em NP pode ser reduzido a ele em tempo polinomial. Portanto, se um único problema NP-completo for resolvido em tempo polinomial, todos os problemas em NP também o serão, estabelecendo P = NP.

Alternativa D — ❌ Incorreta

Algoritmos de aproximação não garantem solução exata; eles fornecem soluções com garantia de qualidade (razão de aproximação), mas não a solução ótima. Garantir a solução exata em tempo polinomial para um problema NP-difícil implicaria P = NP, o que ainda é uma questão em aberto.

NÃO CAIA NESSA!

A chave para entender NP-completude é o conceito de redução polinomial: todos os problemas em NP se reduzem a um problema NP-completo. Se qualquer NP-completo estiver em P, então todos os NP estarão em P. Lembre-se disso para não confundir as definições.

Link permanente: /questoes/qg202007