MO417 - Questão para prova oral

Número: 2013-106

Enunciado: Considere uma versão restrita do problema da satisfatibilidade onde as fórmulas tem até 3 literais por cláusula e podem conter no máximo k ocorrências de cada variável, onde k é fixo. Analise as afirmações abaixo e assinale a alternativa correta.

I - Somente para k > 3 o problema é NP-COMPLETO
II - Para k ≥ 3 o problema é NP-COMPLETO
III - Para k ≤ 2 o problema está em P
IV - O tamanho de k não interfere na complexidade do problema

 Alternativas:

1. II e III estão corretas
2. I e III estão corretas
3. Somente IV está correta
4. Somente II está correta
5. NDA

Ideia original de: Osvaldo Andrade Neto