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

Por
| 

Logotipo do POSCOMP 2019

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

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini. Qualquer valor doado contribui muito para a difusão do conhecimento.

Doar com PagSeguroDoar com PayPal


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário