Algoritmos e Estrutura de Dados · FUNCERN · 2025 | Questão sqc-qg465621

Classes de Complexidade: P, NP, NP-Completo e NP-Difícil

Gabarito: letra B (NP). A classe NP agrupa problemas cuja solução pode ser verificada em tempo polinomial, mesmo que encontrá-la exija tempo exponencial — exatamente o que o enunciado descreve.

A questão explora a diferença fundamental entre as classes de complexidade: P (soluções encontradas em tempo polinomial), NP (soluções verificadas em tempo polinomial), NP-Completo (os problemas mais difíceis dentro de NP) e NP-Difícil (pelo menos tão difíceis quanto NP, mas sem garantia de verificação polinomial). A definição clássica de NP é: problema para o qual, dada uma “certidão” (candidato a solução), é possível confirmar se ela está correta em tempo polinomial, ainda que o processo de busca da solução seja exponencial. É exatamente o contraste proposto.

Classe de Complexidade	Característica de Verificação	Característica de Busca	Enquadramento no Enunciado
P	Rápida (tempo polinomial)	Rápida (tempo polinomial)	❌ Não (busca não é lenta)
NP	Rápida (tempo polinomial)	Lenta (tempo exponencial)	✅ Sim (assimetria descrita)
EXPTIME	Lenta (tempo exponencial)	Lenta (tempo exponencial)	❌ Não (verificação não é rápida)
NP-Difícil	Não necessariamente rápida	Pelo menos tão difícil quanto NP	❌ Não (verificação não é garantida)
NP-Completo	Rápida (tempo polinomial)	Lenta (tempo exponencial)	❌ Parcial (é subclasse de NP, mas a definição geral é NP)

Classes de complexidade: P (Resolve em tempo polinomial, Busca e verificação rápidas); NP (Verifica em tempo polinomial, Busca pode ser exponencial); NP-Completo (Mais difíceis dentro de NP, Redução entre si); NP-Difícil (Pelo menos tão difíceis quanto NP, Verificação não é polinomial)

Alternativa A — ❌ Incorreta

P (Polynomial Time) é a classe dos problemas que podem ser resolvidos em tempo polinomial. Não há distinção entre encontrar e verificar: a própria solução é obtida rapidamente. O enunciado fala de verificação rápida com busca lenta, o que não se encaixa em P.

Alternativa B — ✅ Correta ⟵ GABARITO

NP (Nondeterministic Polynomial Time) é a classe dos problemas para os quais a verificação de uma solução candidata é feita em tempo polinomial, embora encontrar essa solução possa consumir tempo exponencial. A frase “dificuldade de encontrar e facilidade de verificar” é a marca registrada da classe NP.

Alternativa C — ❌ Incorreta

EXPTIME (Exponential Time) abrange problemas que exigem tempo exponencial para serem resolvidos, mas também podem ter verificação exponencial. A característica central da questão é a assimetria entre busca (lenta) e verificação (rápida), o que não é uma propriedade definidora de EXPTIME.

Alternativa D — ❌ Incorreta

NP-Difícil (NP-hard) são problemas pelo menos tão difíceis quanto qualquer problema em NP, mas não necessariamente verificáveis em tempo polinomial. A verificação rápida é condição para estar em NP; NP-Difícil não exige isso. Logo, não atende ao enunciado.

Alternativa E — ❌ Incorreta

NP-Completo (NP-complete) são problemas que são ao mesmo tempo NP e NP-Difícil. Embora todo NP-Completo esteja em NP (portanto, com verificação polinomial), a definição da questão é mais geral: apenas a verificação rápida e busca lenta, sem exigir que seja o “mais difícil” dentro de NP. A classe NP abrange todos os problemas com essa assimetria, incluindo os NP-Completo, mas não se restringe a eles. Portanto, a resposta correta é NP, e não NP-Completo.

PEGA ESSA DICA!

Decore a tríade: P = resolve rápido; NP = verifica rápido, mas pode levar séculos para achar a solução; EXP = resolve em tempo exponencial (verificação também pode ser exponencial). Erro comum é achar que NP significa “não polinomial” — na verdade é “nondeterministic polynomial”. Para cair em prova, lembre-se do exemplo clássico: o problema do caixeiro-viajante (encontrar a rota mínima) está em NP (verificação é simples), mas não se sabe se está em P.

Gabarito: letra B (NP).