¿Está decidiendo la solvabilidad de los sistemas de las ecuaciones cuadráticas con los coeficientes enteros sobre los reales en NP?

Question

En el libro 'Complejidad computacional' por Arora y Barak se plantea la siguiente pregunta (Ejercicio 2.20):

Deja que Realquedeq sea el idioma de todos los conjuntos satisfechos de ecuaciones cuadráticas sobre variables reales. Mostrar que Realquedeq es NP-Completa.

Sé cómo mostrar NP-Dureza, pero estoy atascado cuando se trata de demostrar que este problema está en NP, en particular, cómo demostrar que podemos describir una solución utilizando un número polinomial de bits.

Hice algunas investigaciones y descubrí que sobre los números complejos, sigue siendo una pregunta abierta si el problema está en NP [1]. También parece estrechamente relacionado con la teoría existencial de los reales, lo que de nuevo no se sabe que está en NP.

Por lo tanto, mi pregunta: ¿Este problema se sabe que está en NP? Y si es así, ¿podría alguien apuntarme en la dirección correcta con respecto a la prueba?

---

[1] Pascal Koiran, Nullstellensatz de Hilbert está en la jerarquía polinomial, Journal of Complexity 12 (1996), no. 4, pp. 273-286.

Answer 1

Este problema (generalmente llamado quad) es, de hecho, completa para la teoría existencial de los reales, y así mostrar NP-Membreship sería un resultado fantástico e inesperado.Parece que Arora y Barak pretendían solo pedir una prueba de dureza NP.