Entscheidet die Solvabilität von Systemen von quadratischen Gleichungen mit ganzzahligen Koeffizienten über die Echten in NP?

Question

Im Buch "Computational Complexity" von Arora und Barak ist die folgende Frage (Übung 2.20):

lässt RealQuadeq die Sprache aller ergiebigen Sätze von quadratischen Gleichungen über echte Variablen sein. Zeigen, dass realqueadeq np-komplett ist.

Ich weiß, wie ich NP-Härte zeigt, aber ich bin festgefahren, wenn es darum geht, dass dieses Problem in NP ist, insbesondere wie man zeigen kann, dass wir eine Lösung mit einer Polynomzahl von Bits beschreiben können. .

Ich habe einige Forschungen getan und herausgefunden, dass es über die komplexen Zahlen herausgefunden hat, ob das Problem in NP [1] ist. Es scheint auch eng mit der existenziellen Theorie der Reals verbunden zu sein, was wiederin nicht bekannt ist, dass sie nicht in NP ist.

Somit meine Frage: Ist dieses Problem bekannt, dass er in NP ist? Und wenn ja, könnte mich jemand in die richtige Richtung hinsichtlich des Beweises zeigen.

---

[1] Pascal Koiran, Hilbert's Nullstellenatz ist in der Polynomhierarchie, Journal of Complexity 12 (1996), Nein. 4, pp. 273-286.

Answer 1

Dieses Problem (normalerweise als Quad genannt) ist in der Tat komplett für die existenzielle Theorie der Realen, und somit zeigt die NP-Mitgliedschaft ein fantastisches und unerwartetes Ergebnis.Es scheint, dass Arora und Barak nur beabsichtigt, einen Nachweis der NP-Härte zu bitten.