Variante do Subconjunto-soma tem um $S(1)$ algoritmo se $Goldbach$ é verdadeiro

Question

Dado $S$ de números inteiros positivos $>$ $1$ há alguns combinação com mesmo $SOMA$ > $2$ que é NÃO a soma de dois primos?

$SOMA$ = 10

$S$ = $[4,6]$

$Não$,

Soma de Dois Primos $5 + 5 = 10$.

Combinação $4+6=10$

Ele tem um $S(1)$ algoritmo de se Goldbach é Verdade (sempre de saída $NÃO$).Caso contrário, ele parece ser NP-completo, pois seria necessário resolver Subconjunto-Soma.

Pergunta

Será um de muitos-uma redução de $Subconjunto-soma$ trabalho para este problema de decisão em poli-tempo?

Answer 1

Se há um número finito de exceções para a conjectura de Goldbach, em seguida, ele ainda é resolvido em tempo linear.

Note que existe uma probabilidade não-zero que a conjectura de Goldbach é falso.Heuristicamente, a probabilidade de um número infinito de exceções é zero.