Será que esta redução da Cobertura Exata em Subconjunto-Soma falhar devido a um potencial de falso-positivo?

Question

Após a remoção de multi-conjuntos e conjuntos de elementos que não existem na $S$.

$S$ = $[9,6,7,4,5,1,8]$

$C$ =$[[9,6,7],[4,5],[1,8]]$

Transformar os valores em $C$ de valores de índice com $S$.(Isso deve ser feito antes de tocar $S$)

$C$ = $[[1,2,3],[4,5],[6,7]]$

E fazer o mesmo para $S$

$S$ = $[1,2,3,4,5,6,7]$

Quadrado de cada $x$ inteiro em ambos os $S$ e $C$

$f(x)$ = $x^2$, $x ∈ S$ em seguida, $C$

$S$ = $[1, 4, 9, 16, 25, 36, 49]$

$C$ = $[[1,4,9],[16,25],[36,49]]$

Em seguida, remova todos os conjuntos, com a repetição de quantias para evitar falsos positivos.Isto significa que não $[1],[1]s...$ que poderia ser utilizado, a soma total soma de $S$, Isso também significa que $[1,4,9]$ ou $[4,9,1]$.(deixe um porém!)

1. Após a transformação está completa usar subconjunto-soma de problemas e definir total-soma como $140$ (total-soma dos $s$)
2. Definir lista de números inteiros, como resumiu conjunto de $C$ = $[[14],[41],[85]]$
3. Executar o Algoritmo e obter a solução

Pergunta

Será que esta redução da Cobertura Exata em Subconjunto-Soma de todas produzir um falso positivo?

Answer 1

Se você não estiver realmente tiver certeza se uma redução do trabalho, provavelmente não.Sempre que você está fazendo uma redução de você deve sempre ter um plano de como provar que é correto.

Neste caso, nós estamos olhando para ver se $1^2+2^2+3^2+...+n^2$ pode ser escrito como uma soma de quadrados, de alguma outra forma (o que seria um falso-positivo).

Temos que $4^2=2^2+2^2+2^2+2^2$.Isso é o suficiente para construir um contra-exemplo.

Deixe $S=\{1,2,3,4,5,6,7\}$ e $C=\{\{1,2\},\{2,3\},\{2,5\},\{2,6\}\,\{2,7\},\{1,3,4,5,6,7\}\}$.

Não há cobertura exata (a única forma de obter $4$ é para tomar $\{1,3,4,5,6,7\}$ mas então nós não podemos tomar qualquer outra, pois todas elas se sobrepõem).

No entanto, temos que:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Assim, podemos concluir que a redução não funciona.