Questão 42 — Classes P e NP — Redução Polinomial (Teoria da Computação) — Escola de Formação Complementar do Exército (EsFCEx) · Exército Brasileiro 2019

Teoria da Computação Classes P e NP — Redução Polinomial

Escola de Formação Complementar do Exército (EsFCEx) 2019

Exército Brasileiro · Oficial do Quadro Complementar (CFO/QC) — Informática · Caderno Tipo A

Gabarito disponível

Segundo Thomas Cormen, cientistas da computação geralmente consideram problemas resolvíveis por algoritmos de tempo polinomial como “tratáveis”, o que quer dizer “fácil de lidar”. Se existir um algoritmo de tempo polinomial para um problema, então se diz que esse problema está na classe P. A respeito dos algoritmos de redução em tempo polinomial, assinale a alternativa correta.

Selecione uma alternativa A) Se o problema X é NP-completo e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y se torna da classe P. B) Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y pode ser NP-difícil. C) Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y depende da ordem de complexidade. D) Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y é NP-difícil também. E) Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y não é NP-difícil.

Resolução comentada

Redução polinomial de um problema NP-difícil X para Y torna Y NP-difícil.

Se X é NP-difícil e X ≤p Y, então todo problema em NP reduz a X e, por transitividade, a Y em tempo polinomial. Logo Y é pelo menos tão difícil quanto X, ou seja, NP-difícil.

Análise das alternativas

A) Errada: reduzir um NP-completo a Y não coloca Y em P (isso só ocorreria se P=NP, e não é consequência da redução). B) Errada: 'pode ser' é impreciso; a conclusão é necessária, Y é NP-difícil. C) Errada: afirmação sem sentido técnico; a classificação não depende de 'ordem de complexidade' nesse contexto. E) Errada: contradiz a transitividade das reduções.

Referência: Cormen et al., Algoritmos: Teoria e Prática – NP-completude

Resolução comentada do VaiConcursos.