Reduzindo a cobertura exata para a soma de subconjuntos

Mostre que o problema da soma do subconjunto (Dada uma sequência de números inteiros e um número , existe uma subsequência de que soma exatamente ?) Está NP-completo.$S=i_1, i_2, \dots , i_n$$k$$S$$k$

Dica: Use o problema exato da capa.

O problema exato da capa é o seguinte: Dada uma família de conjuntos existe uma capa de conjunto que consiste em uma subfamília de conjuntos separados por pares?$S_1, S_2, \dots , S_n$

Primeiro de tudo, para mostrar que esse problema está em , precisamos fazer o seguinte?$\mathcal{NP}$

Uma máquina de Turing não determinística pode primeiro adivinhar qual é a subsequência daquilo que estamos procurando e depois verificar se ela soma exatamente k em tempo linear. Isso está correto?

Para mostrar que o NP está completo, como podemos reduzir o problema exato de cobertura para subconjuntos de soma? É o seguinte?

O problema exato de cobertura tem uma solução se cada elemento estiver em exatamente um conjunto.

Consideramos o conjunto e o número modo que cada número corresponde a um conjunto de elementos e corresponde a todo o conjunto. Suponha que haja elementos conjuntos diferentes.$S$$k$$k$$n$$k$

Substituímos cada conjunto S por um número que seja em sua i-ésima posição se i estiver em S e tiver um em sua i-ésima posição.$1$$0$

Definimos k como um número que é cópias do número .$n$$1$

Ideia básica : no problema exato da capa, cada elemento é reduzido a um número. Então, cada conjunto é reduzido à soma dos números que cobre. Por fim, defina como a soma de todos os números.$k$

Essa redução sempre funciona de uma maneira: se existe uma solução para o problema exato de cobertura, também existe uma solução para o problema de soma de subconjuntos.

A parte difícil é provar o contrário. Números triviais não funcionam. Suponha que os elementos sejam reduzidos a e os conjuntos sejam$1,2,3,4$

• $S_1=\{3,4\}$
• $S_2=\{3\}$

A redução na soma do subconjunto são os números e , que retornam SIM, mas não há solução para o problema exato de cobertura!$7,3$$k=10$

Precisamos ser mais inteligentes na escolha dos números. Percebeu que a falha nos números anteriores é que pode substituir . Não queremos que nenhum número seja substituído. Portanto, queremos que os números tenham lacunas suficientemente grandes. Suponha que em um problema exato de cobertura de elementos, o primeiro elemento seja reduzido para . Qual o tamanho do segundo número? Existem conjuntos que podem incluir o primeiro número. Portanto, o segundo elemento deve ser reduzido para um número maior que modo que, não importa quantas vezes apareça, ele não poderá substituir o segundo número. Vamos reduzir o segundo elemento para$3$ $1,2$$n$$1$$2^{n-1}$$2^{n-1}$$1$$2^n$. O mesmo argumento se aplica ao terceiro argumento, então o reduzimos para .$2^n\times 2^n=4^n$

Em conclusão, o $i$-ésimo elemento no problema exato da capa tem um valor de $2^{in}$. Cada conjunto é reduzido à soma dos números que cobre.

Agora mostramos que a cobertura exata está no NP-Hard. Precisamos provar que ele também está no NP para mostrar que é NP-Complete. Eu acho que é relativamente simples. Se precisar de ajuda para isso, darei algumas dicas para você.

A soma do subconjunto pode ser facilmente transformada a partir do problema da partição. A prova de reduzir a capa exata é semelhante à da correspondência tridimensional e você pode encontrá-la no livro de Garey e Johnson. A prova é um pouco complicada.