MO417 - Questão para a prova oral

Número: 116

Enunciado:
Analise as seguintes afirmativas.

1. Se existisse uma resolução em tempo polinomial para o problema da satisfabilidade de circuitos, então P = NP.
2. Toda tautologia é capaz de satisfação.
3. A classe NP é fechada sob o complemento, ou seja, NP = co-NP
4. Se P = NP, então todos os problemas de decisão pertencem à classe NP-Difícil.

1. Apenas as afirmativas I, II e IV estão corretas.
2. Apenas as afirmativas I, III e IV estão corretas.
3. Apenas as afirmativas II e III estão corretas.
4. Todas as afirmativas estão corretas.
5. NDA

Autor(a): Thiago Augusto Lopes Genez