Um problema de decisão em $NP$ deve ter um complemento em $Co-NP$, se eu puder verificar as soluções em tempo polinomial?

Question

A conjectura de Goldbach diz que todo número inteiro par $>$ $2$ pode ser expresso como a soma de dois primos.

Digamos $N$ é a nossa contribuição e sua $10$.Que é um número inteiro > 2 e não é ímpar.

Algoritmo

1.Crie uma lista de números de $1, para ~N$

2. Use algoritmo de teste principal para criar uma segunda lista de números primos

3. Use meu solucionador 2_sum que permite usar números primos duas vezes nessa soma $N$

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

4.Verifique a solução de forma eficiente

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

5.Saída

yes 7 + 3
Solution is correct

Pergunta

Se a conjectura for verdadeira, a resposta será sempre sim.Isso significa que não pode estar em $Co-NP$ porque a resposta é sempre Sim?

Answer 1

Acho que você pode estar confundindo algumas coisas.

Primeiro, o complemento de qualquer problema em NP está em CoNP por definição.Nenhuma condição adicional é necessária.Em segundo lugar, admitir um algoritmo de tempo polinomial para verificar soluções, e pertencer à classe NP, são afirmações equivalentes.

Terceiro, a conjectura de Goldbach é uma afirmação matemática que, segundo os axiomas padrão, é verdadeira ou falsa.Isso significa que como um problema de decisão, da mesma forma que qualquer outra afirmação matemática, a conjectura de Goldbach tem uma solução em tempo constante:a máquina A responde "verdadeiro", a máquina B responde "falso".Necessariamente um deles está certo e ambos levam tempo constante.Obviamente, isso não ajuda em nada.

Então você provavelmente quis perguntar sobre o problema que, dado um número inteiro par N > 2, pede que você decida se ele pode ser expresso como a soma de dois primos.Este problema está de fato em NP como você disse, porque se N = p + q para primos p, q.Então $\esquerda<p,q\direita>$ é uma solução que pode ser verificada em tempo polinomial, usando o algoritmo poli-tempo para primeiro verificar se p e q são de fato primos e, em seguida, qualquer algoritmo de adição.Não sei se existe um algoritmo de tempo polinomial para esse problema, mas não ficaria surpreso se existisse.

Se a conjectura de Goldbach for verdadeira, então a máquina que responde “sim” sem sequer olhar para a entrada aceita a linguagem descrita acima e funciona em tempo constante.