Número:
Enunciado: O problema da soma de um subconjunto é definido como: dado um conjunto S finito de inteiros positivos e um alvo t também inteiro positivo, deseja-se saber se há um subconjunto de S cuja a soma é igual ao alvo t. Esse problema é NP-Completo. Uma definição dele é dada abaixo e, como padrão, os dados de entrada são codificados em binário.
Enunciado: O problema da soma de um subconjunto é definido como: dado um conjunto S finito de inteiros positivos e um alvo t também inteiro positivo, deseja-se saber se há um subconjunto de S cuja a soma é igual ao alvo t. Esse problema é NP-Completo. Uma definição dele é dada abaixo e, como padrão, os dados de entrada são codificados em binário.
SUBSET-SUM = {(S,t) : existe um subconjunto S' ⊆ S tal que t = ∑[n ∈ S'] n}
Se restringirmos o conjunto S para apenas poder conter inteiros que são
potências de 2, qual das afirmações abaixo sobre o novo problema é
verdadeira?
I - O problema continua a ser NP-Completo.
II - O problema pertence à classe NP.
III - O problema pertence à classe co-NP.
a) I e IIIdeia original de: René du Raymond Sacramento
b) Apenas a II
c) Apenas a III
d) II e III
e) N.D.A.
Nenhum comentário:
Postar um comentário