La variante du sous-ensemble-SUM a un algorithme $ O (1) $ si $ goldbach $ est vrai
-
29-09-2020 - |
Question
donné $ s $ d'entiers positifs $> $ $ 1 $ Y a-t-il une certaine combinaison avec
$ somme $ = 10
$ s $ = $ [4,6] $
no $ no $ ,
somme de deux nombres premiers 5 $ + 5= 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?
La solution
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.