La variante du sous-ensemble-SUM a un algorithme $ O (1) $ si $ goldbach $ est vrai

Question

donné $ s $ d'entiers positifs $> $ $ 1 $ Y a-t-il une certaine combinaison avec même $ SUM $ > $ 2 $ $ c'est pas la somme de deux prime ?

$ somme $ = 10

$ s $ = $ [4,6] $

no $ no $ ,

somme de deux nombres premiers 5 $ + 5= 10 $ .

combinaison 4 $ + 6= 10 $

Il a une $ O (1) $ algorithme si Goldbach est vrai (toujours la sortie no $ no $ ). Sinon, cela semblerait être NP-complet car il nécessiterait la résolution de la somme sous-ensembles.

Question

une réduction de $ Sous-Sum $ Travailler pour ce problème de décision en poly-time?

Answer 1

S'il y a un nombre fini d'exceptions à la conjecture Goldbach, il est encore solvable en temps linéaire.

Notez qu'il existe une probabilité non nulle que la conjecture Goldbach est fausse.Heuriste, la probabilité d'un nombre infini d'exceptions est nulle.