La variante de Subset-sum tiene un algoritmo $O(1)$ si $Goldbach$ es verdadero

Question

Dado $S$ de enteros positivos $>$ $1$ ¿Hay alguna combinación con incluso $SUM$ > $2$ eso es NO la suma de dos primos?

$SUM$ = 10

$S$ = $[4,6]$

$No$,

Suma de dos primos $5 + 5 = 10$.

Combinación $4+6=10$

tiene un $O(1)$ algoritmo si Goldbach es Verdadero (siempre genera $NO$).De lo contrario, parecería ser NP-completo porque requeriría resolver Subconjunto-Suma.

Pregunta

¿Se producirá una reducción de muchos uno de $Subconjunto-suma$ ¿Funciona para este problema de decisión en poli-tiempo?

Answer 1

Si hay un número finito de excepciones a la conjetura de Goldbach, aún es solucible en tiempo lineal.

Tenga en cuenta que hay una probabilidad que no tiene cero que la conjetura Goldbach sea falsa.Heurísticamente, la probabilidad de un número infinito de excepciones es cero.