A que classe de complexidade pertence esse problema da teoria dos números?

12

'Dado a,b,cN , existe x,yN , ax2+by=c ' é NP completo.

A qual classe de complexidade 'Dado a,b,cN , existe x,yN , ax2+by2=c ' pertence?


fonte
2
Por que o primeiro problema é NP-completo? Uma referência seria apreciada. :)
Michael Wehar
2
@ MichaelWehar, o diofantino quadrático é NP-completo. Eu acho que é mesmo em Gary e Johnson.
Kaveh
2
É AN8 em Garey e Johnson, página 250: Manders e Adleman, "NP - problemas de decisão completos para quadráticos binários", 1978.
Kaveh
4
A existência de soluções racionais é polinomialmente redutível à fatoração, portanto, em NPcoNP : usando o princípio de Hasse , equivale a verificar se o símbolo de Hilbert (a/c,b/c)p=1 para todos os primos p2abc .
Emil Jeřábek 3,0
5
a=b=1cc cp3(mod4)cc

Respostas:

5

Adicionado mais tarde: Conforme observado nos comentários, o limite superior do NP é trivial se a, bec são positivos, como foi solicitado.

O teorema 1.2 deste artigo mostra que decidir se uma determinada equação diofantina em duas variáveis ​​tem uma solução está em NP.

Manu
fonte
3
Não é uma boa resposta (afirma o óbvio).
2
Isso parece responder à pergunta que foi feita. Se você pretendia outras condições, precisará incluí-las na pergunta.
András Salamon
4
@ AndrásSalamon, isso não acontecer, o NP limite superior parece trivial quando e são ambos não negativo (para e são polinomialmente delimitada por em , , e ). A verdadeira questão é se é difícil para NP. b x y a b cabxyabc
Kaveh
1
@ Kaveh: sim, mas não foi isso que foi perguntado. Além disso, presumo que a, b, c sejam dados em binário, então x e y são apenas exponencialmente delimitados em n?
András Salamon
4
@ AndrásSalamon, Seu tamanho é polinomialmente delimitado em . Como eu disse, estar no NP é trivial para o problema. O artigo está falando de um caso mais geral, do qual a questão não se refere. n
Kaveh