Die Variante der Subset-Summe hat einen $ O (1) -Algorithmus, wenn $ Goldbach $ true ist

Question

gegeben $ s $ von positiven ganzzungen $> $ $ 1 $ Gibt es eine Kombination mit sogar $ sum $ > $ 2 $ das ist nicht die Summe von zwei primes

$ Sum $ = 10

$ s $ = $ [4,6] $

$ NO $ ,

Summe von zwei Primzahlen 5 + 5= 10 $ .

Kombination $ 4 + 6= 10 $

es hat einen $ O (1) $ Algorithmus, wenn goldbach ist wahr (immer ausgeben $ no $ ). Andernfalls scheint es np-komplett zu sein, da er das Lösen der Subset-Summe erfordern würde.

Frage

wird eine Vieler-One-Reduktion von $ Subset-sum $ für dieses Entscheidungsproblem in der Poly-Zeit?

Answer 1

Wenn es eine endliche Anzahl von Ausnahmen von der Goldbach-Vermutung gibt, ist es in der linearen Zeit noch lösbar.

Beachten Sie, dass es eine Wahrscheinlichkeit ungleich Null gibt, dass die Goldbach-Vermutung falsch ist.Heuristisch ist die Wahrscheinlichkeit für eine unendliche Anzahl von Ausnahmen Null.