Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCM 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq337483
Banca
FCM
Órgão
IFN-MG
Ano
2018
Nível
Superior
Cargo
Ciências da Computação: Teoria da Computação
Avalie as afirmações abaixo:I. A classe P e a classe NP são disjuntas.II. A classe P é um subconjunto da classe co-NP.III. Problemas coNP-completos admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial.IV. A interseção das classes NP e co-NP é vazia.Está correto apenas o que se afirma em
AI e III.
BI e IV.
CI, II e IV
DII, III.
EII e IV.
Revelar gabarito e comentário▾
GabaritoD — II, III.
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”.
Classes de complexidade P, NP e co-NP
Gabarito: letra D. Estão corretas apenas as afirmações II e III. A afirmação I é falsa porque P ⊆ NP (não são disjuntas). A afirmação IV é falsa porque P ⊆ NP ∩ co-NP, portanto a interseção não é vazia. A afirmação II é verdadeira: todo problema em P tem seu complemento também em P, logo pertence a co-NP. A afirmação III é verdadeira: problemas coNP-completos, por definição, permitem verificar uma resposta negativa em tempo polinomial com um certificado (já que estão em co-NP).
Afirmação I — ❌ Incorreta
Afirma que P e NP são disjuntas. Na verdade, sabe-se que P ⊆ NP (todo problema resolvível em tempo polinomial também é verificável em tempo polinomial). Logo, a interseção entre P e NP é o próprio P, que não é vazio. A relação exata entre P e NP é um problema em aberto, mas certamente não são disjuntas.
Afirmação II — ✅ Correta
A classe P é fechada sob complemento: se um problema está em P, seu complemento também está em P. Portanto, todo problema em P também está em co-NP (pois co-NP contém os problemas cujo complemento está em NP, e P ⊆ NP). Assim, P ⊆ co-NP.
Afirmação III — ✅ Correta
Por definição, um problema pertence a co-NP se seu complemento está em NP. Para problemas coNP-completos (os mais difíceis em co-NP), existe um certificado para verificar em tempo polinomial que uma instância NÃO pertence ao problema (resposta negativa). Isso é exatamente o que a afirmação descreve: "admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial".
Afirmação IV — ❌ Incorreta
Afirma que a interseção NP ∩ co-NP é vazia. Entretanto, P ⊆ NP ∩ co-NP, pois todo problema em P está tanto em NP quanto em co-NP. Logo, a interseção contém pelo menos todos os problemas de P, não sendo vazia.
Classes P, NP e co-NP — só NP: NP \ (P ∪ co-NP); só co-NP: co-NP \ (P ∪ NP); só P: ∅; NP∩co-NP: NP ∩ co-NP \ P; NP∩P: P; co-NP∩P: P; NP∩co-NP∩P: P