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]$


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.


Will a many-one-reduction from $Subset-sum$ work for this decision problem in poly-time?

  • $\begingroup$ It's a very special instance of subset sum. I don't see how you'd reduce general subset sum to this particular case. $\endgroup$ – Yuval Filmus Jun 21 '20 at 21:17
  • $\begingroup$ @YuvalFilmus As a function problem (output subset-sum with integers) is virtually the same for the general subset-sum with the exception that the answer is always NO if the conjecture is true. $\endgroup$ – Dingle Berry Jun 21 '20 at 22:50

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.

  • $\begingroup$ Mathematically, has it been proven to be an infinite number of exceptions to the Goldbach Conjecture? (In the sense, $IF$ proven false)? Anyway, thanks for the answer! $\endgroup$ – Dingle Berry Jun 23 '20 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.