MO417 - Questão para a prova oral

Número: 2013-105

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, quais das afirmações abaixo sobre o novo problema são verdadeiras?


I - O problema continua a ser NP-Completo.
II - O problema pertence à classe NP.
III - O problema pertence à classe co-NP.

1. Apenas a II 
2. Apenas a III 
3. I e II
4. II e III
5. N.D.A.

Ideia original de: René du Raymond Sacramento