# 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. May 17, 2020 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. May 17, 2020 at 19:23

I think you might be confusing a couple of things.

First, the complement of any problem in NP is in CoNP by definition. No further conditions are required. Second, admitting a polynomial time algorithm to verify solutions, and belonging to the class NP, are equivalent statements.

Third, Goldbach's conjecture is a mathematical statement, which under standard axioms is either true or false. That means that as a decision problem, in the same fashion that any other mathematical statement, Goldbach's conjecture has a constant time solution: machine A answers "true", machine B answers "false". Necessarily one of them is right, and they both take constant time. Obviously this is not helpful at all.

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.

If Goldbach's conjecture is true, then the machine that answers "yes" without even looking at the input accepts the language described above and runs in constant time.

• Well, for one thing for sure there's definitely pseudo-polynomial solution. May 19, 2020 at 0:26