# Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

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?

• It's a very special instance of subset sum. I don't see how you'd reduce general subset sum to this particular case. – Yuval Filmus Jun 21 '20 at 21:17
• @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. – Dingle Berry Jun 21 '20 at 22:50

• 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! – Dingle Berry Jun 23 '20 at 1:52