Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true
-
29-09-2020 - |
Question
Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $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?
Solution
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.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange