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

'Dado $a,b,c\in\Bbb N$ , existe $x,y\in\Bbb N$ , $ax^2+by=c$ ' é $\mathsf{NP}$ completo.

A qual classe de complexidade 'Dado $a,b,c\in\Bbb N$ , existe $x,y\in\Bbb N$ , $ax^2+by^2=c$ ' pertence?

ds.algorithms complexity-classes reductions nt.number-theory np-complete
fonte

Por que o primeiro problema é NP-completo? Uma referência seria apreciada. :)

Michael Wehar

@ MichaelWehar, o diofantino quadrático é NP-completo. Eu acho que é mesmo em Gary e Johnson.

Kaveh

É AN8 em Garey e Johnson, página 250: Manders e Adleman, "NP - problemas de decisão completos para quadráticos binários", 1978.

Kaveh

A existência de soluções racionais é polinomialmente redutível à fatoração, portanto, em

N P \cap c o N P

$\mathrm{NP}\cap\mathrm{coNP}$ : usando o princípio de Hasse , equivale a verificar se o símbolo de Hilbert

(a / c, b / c)_{p} = 1

$(a/c,b/c)_p=1$ para todos os primos

p ∣ 2 a b c

$p\mid2abc$ .

Emil Jeřábek 3,0

a = b = 1

$a=b=1$

c

$c$

p \equiv 3 (\mod 4)

$p\equiv3\pmod4$

c

$c$

c

$c$

Respostas:

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

Não é uma boa resposta (afirma o óbvio).

Isso parece responder à pergunta que foi feita. Se você pretendia outras condições, precisará incluí-las na pergunta.

András Salamon

@ 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.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

Kaveh

@ 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

@ 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

$n$

Kaveh