Décider de la solvabilité des systèmes d'équations quadratiques avec des coefficients entier sur les réels du NP?

Question

Dans le livre "Complexité de calcul" de ARORA et de BARAK, la question suivante est posée (exercice 2.20.):

Laissez RealQuadQ Soyez la langue de tous les ensembles satisfiables d'équations quadratiques sur des variables réelles. Montrer que realquadeq est NP-complet.

Je sais comment montrer la dureté np-dureté, mais je suis bloqué lorsqu'il s'agit de prouver que ce problème est dans NP, en particulier comment montrer que nous pouvons décrire une solution à l'aide d'un nombre polynomial de bits.

J'ai fait des recherches et j'ai découvert que sur les chiffres complexes, il reste une question ouverte si le problème est dans NP [1]. Il semble également apparenté étroitement à la théorie existentielle des réels, qui n'est à nouveau pas connue pour être dans NP.

Ainsi, ma question: Ce problème est-il connu pour être dans NP? Et si oui, quelqu'un pourrait-il me diriger dans la bonne direction concernant la preuve.

---

[1] Pascal Koiran, Hilbert's Nullstellensatz est dans la hiérarchie polynomiale, journal de complexité 12 (1996), no. 4, pp. 273-286.

Answer 1

Ce problème (généralement appelé quad) est en fait complet pour la théorie existentielle des réelles, et ainsi montrant ainsi l'abonnement NP serait un résultat fantastique et inattendu.Il semble que ARORA et BARAK envisagent uniquement de demander une preuve de la dureté NP.