Un problème de décision dans $ NP $ a-t-il un complément en $ CO-NP $, si je peux vérifier les solutions à des polynômes?

Question

la conjecture de Goldbach indique chaque entiers $> $ $ 2 $ peut être exprimé comme la somme de deuxnombres premiers.

disons $ n $ est notre entrée et son 10 $ .Qui est un entier> 2 et n'est pas étrange.

Algorithme

1.Créez la liste des nombres de 1 $, à ~ n $

2.Utilisez l'algorithme d'essai principal pour créer une deuxième liste de nombres premiers

3.Utilisez mon solveur de 2_sum qui vous permet d'utiliser des prime deux fois cela résumant jusqu'à $ N $

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

4.Verify Solution Efficentement

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

Si la conjecture est vraie, la réponse sera toujours oui.Cela signifie-t-il que cela ne peut pas être dans $ co-np $ car la réponse est toujours oui?

Answer 1

Je pense que vous pourriez vous confondre quelques choses.

Premièrement, le complément de tout problème dans NP est dans la définition de ConP. Aucune autre condition n'est requise. Deuxièmement, admettant un algorithme de temps polynomial pour vérifier les solutions et appartenir à la classe NP, sont des déclarations équivalentes.

Troisième, la conjecture de Goldbach est une déclaration mathématique, qui sous les axiomes standard est soit vraie, soit fausse. Cela signifie que comme un problème de décision, de la même manière que toute autre déclaration mathématique, la conjecture de Goldbach a une solution de temps constante: la machine a des réponses "vraie", la machine B répond "False". Nécessairement l'un d'entre eux a raison et ils prennent tous les deux une durée constante. Évidemment, cela n'est pas utile du tout.

Donc, vous vouliez probablement poser des questions sur le problème qui étant donné qu'un entier N> 2 vous demande de décider si cela peut être exprimé comme la somme de deux nombres premiers. Ce problème est en effet dans NP comme vous l'avez dit, car si n= p + q pour les prime P, q. Alors $ \ gauche $ est une solution pouvant être vérifiée en temps polynomial, en utilisant l'algorithme poly-time pour vérifier la première fois que p et q sont en effet des nombres premiers, puis n'importe quel algorithme d'addition. Je ne sais pas s'il y a un algorithme de temps polynomial pour ce problème, mais je ne serais pas surpris s'il y en a un.

Si la conjecture de Goldbach est vraie, la machine qui répond «oui» sans même regarder l'entrée accepte la langue décrite ci-dessus et fonctionne en temps constant.