# Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?

Goldbach's Conjecture says every even integer $$>$$ $$2$$ can be expressed as the sum of two primes.

Let's say $$N$$ is our input and its $$10$$. Which is an integer > 2 and is not odd.

## Algorithm

1.Create list of numbers from $$1,to~N$$

2.Use prime-testing algorithm for creating a second list of prime numbers

3.Use my 2_sum solver that allows you to use primes twice that sum up to $$N$$

for j in range(list-of-primes)):
if N-(list-of-primes[j]) in list-of-primes:
print('yes')
break


4.Verify solution efficently

if AKS-primality(N-(list-of-primes[j])):
if AKS-primality(list-of-primes[j]):
print('Solution is correct')


5.Output

yes 7 + 3
Solution is correct


## Question

If the conjecture is true, then the answer will always be Yes. Does that mean it can't be in $$Co-NP$$ because the answer is always Yes?

• Wait! It would be in $P$, because the complement would be decidable in poly-time! I think I confused myself and I'll leave my question here for others to answer so that it could be useful for others. – Dingle Berry May 17 at 19:02
• Welcome to CS.SE! If you think you solved your problem, feel free to create an answer for your own question. This way, your question and answer can be useful for others, as you mentioned. – Discrete lizard May 17 at 19:23

So you probably meant to ask about the problem that given an even integer N > 2 asks you to decide whether it can be expressed as the sum of two primes. This problem is indeed in NP as you said, because if N = p + q for primes p, q. Then $$\left$$ is a solution that can be verified in polynomial time, by using the poly-time algorithm to first check that p and q are indeed primes, and then any addition algorithm. I don't know if there is a polynomial time algorithm for this problem, but I wouldn't be surprised if there is one.