Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true Given $S$ of positive integers $&gt;$ $1$ is there some combination with even $SUM$ &gt; $2$ that is NOT the sum of two primes?
$SUM$ = 10
$S$ = $[4,6]$
$No$,
Sum of Two Primes
$5 + 5 = 10$.
Combination $4+6=10$
It has an $O(1)$ algorithm if Goldbach is True (always output $NO$). Otherwise, it would seem to be NP-complete because it would require solving Subset-Sum.
Question
Will a many-one-reduction from $Subset-sum$ work for this decision problem in poly-time?
If there is a finite number of exceptions to the Goldbach conjecture then it is still solvable in linear time.
Note that there is a non-zero probability that the Goldbach conjecture is false. Heuristically, the probability for an infinite number of exceptions is zero.