Número:
Enunciado: Considere uma versão restrita do problema da satisfabilidade onde as fórmulas podem conter no máximo k ocorrências de cada variável e que 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 pode ser resolvido em tempo polinomial
IV - O tamanho de K não interfere na classificação do problema
Alternativas:
a) Somente I está correta
b) Somente IV está correta
c) II e III estão corretas
d) Somente II está correta
e) NDA
Idéia original de: Osvaldo Andrade Neto
Enunciado: Considere uma versão restrita do problema da satisfabilidade onde as fórmulas podem conter no máximo k ocorrências de cada variável e que 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 pode ser resolvido em tempo polinomial
IV - O tamanho de K não interfere na classificação do problema
Alternativas:
a) Somente I está correta
b) Somente IV está correta
c) II e III estão corretas
d) Somente II está correta
e) NDA
Idéia original de: Osvaldo Andrade Neto
Nenhum comentário:
Postar um comentário