1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dingle Berry May 17 at 19:02
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard May 17 at 19:23
2
$\begingroup$

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<p,q\right>$ 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well, for one thing for sure there's definitely pseudo-polynomial solution. $\endgroup$ – Dingle Berry May 19 at 0:26

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.