POSCOMP 2019: Questão 40 Resolvida (Linguagens Formais e Autômatos)

Questão

Considere as seguintes afirmações sobre classes de problemas:

1. O problema de decisão CAM, descrito a seguir, pertence à classe de complexidade P.

   CAM (caminho em grafo)
   Entrada: uma tripla (G,a,b) em que

   • G é um grafo
   • a e b são nodos de G

   Pergunta: Existe caminho em G iniciando em a e terminando em b?

2. Um problema X pertence à classe de problemas NP-completos quando satisfaz às seguintes condições:

   • X pertence à classe NP, e
   • todo problema Y da classe NP pode ser reduzido em tempo polinomial a X.

3. Se um problema de decisão X pertence à classe P, então o complemento do problema X (problema com as mesmas instâncias que X, porém com as respectivas respostas invertidas) pertence à classe NP.

Quais estão corretas?

• (A) Apenas I.
• (B) Apenas III.
• (C) Apenas I e II.
• (D) Apenas II e III.
• (E) I, II e III.

Resolução

A afirmação I está correta. O problema de verificar se existe um caminho entre dois vértices num grafo pode ser resolvido utilizando os algoritmos de busca em grafos (busca em largura ou em profundidade, por exemplo), cuja complexidade é polinomial, portanto de classe P.

Poderíamos até mesmo utilizar um dos algoritmos de caminhos mínimos para resolver o problema, que também são polinomiais.

A afirmação II é verdadeira e define corretamente os problemas NP-completos, dispensando explicações.

Finalmente, a afirmação III também está correta. A classe de problemas P é fechada em seu complemento, ou seja, co-P também é P. Como consequência, o complemento de um problema da classe P também pertence à classe P e, como todo problema P também é NP, então o complemento também será NP.

Portanto, a alternativa correta é a E.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Referências

• [1] FEOFILOFF, P. Complexidade: problemas NP-completos. São Paulo: IME-USP, 2018. Acesso em 24 de março de 2020.
• [2] SRBA, J. Computability and Complexity. Aalborg University. Acesso em 24 de março de 2020.