¿A qué clase de complejidad pertenece este problema de teoría de números?

'Dado , ¿hay , ' es -completo? $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by=c$ $\mathsf{NP}$

¿A qué clase de complejidad pertenece 'Dado , a qué pertenece , '? $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by^2=c$

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

¿Por qué es el primer problema NP-completo? Se agradecería una referencia. :)

Michael Wehar

@MichaelWehar, la diofantina cuadrática tiene NP completo. Creo que incluso en Gary y Johnson.

Kaveh

Es AN8 en Garey y Johnson, página 250: Manders y Adleman, "Problemas de decisión de NP completo para las cuadráticas binarias", 1978.

Kaveh

La existencia de soluciones racionales es polinomialmente reducible a factorización, por lo tanto, en

: usando el principio de Hasse , equivale a verificar que el símbolo de Hilbert

para todos los primos

N P \cap c o N P

$\mathrm{NP}\cap\mathrm{coNP}$

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

$(a/c,b/c)_p=1$

p ∣ 2 a b c

$p\mid2abc$

Emil Jeřábek

a = b = 1

$a=b=1$

c

$c$

p \equiv 3 (\mod 4)

$p\equiv3\pmod4$

c

$c$

c

$c$

Respuestas:

Agregado más tarde: como se señaló en los comentarios, el límite superior de NP es trivial si a, byc son positivos, como se preguntó.

El teorema 1.2 en este artículo muestra que decidir si una ecuación de diofantina dada en dos variables tiene una solución está en NP.

Manu
fuente

No, esta es una buena respuesta (dice lo obvio).

Esto parece responder a la pregunta que se hizo. Si tenía la intención de otras condiciones, debe incluirlas en la pregunta.

András Salamon

@ AndrásSalamon, no lo hace, la NP límite superior parece trivial cuando y son ambos no negativos (por lo que y son polinomialmente delimitada por en , , y ). La verdadera pregunta es si es difícil para NP.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

Kaveh

@Kaveh: sí, pero eso no fue lo que se le preguntó. Además, supongo que a, b, c se dan en binario, por lo que x e y están limitadas exponencialmente en n?

András Salamon

@ AndrásSalamon, Su tamaño está polinómicamente limitado en . Como dije, estar en NP es trivial para el problema. El documento habla de un caso más general del que no se trata la pregunta.

n

$n$

Kaveh