Sta decidendo la solvibilità dei sistemi di equazioni quadratiche con i coefficienti interi sui reali in NP?

Question

Nel libro 'complessità computazionale' di Arora e Barak è posta la domanda seguente (esercizio 2.20.):

.

Lascia che Realquadeq sia la lingua di tutti gli insiemi soddisfatti di equazioni quadratiche su variabili reali. Mostra che Realquadeq è NP-Completo.

So come mostrare la durezza NP, ma sono bloccato quando si tratta di dimostrare che questo problema è in NP, in particolare come dimostrare che possiamo descrivere una soluzione usando un numero polinomiale di bit. Ho fatto qualche ricerca e ho scoperto che oltre i numeri complessi, rimane una domanda aperta se il problema è in NP [1]. Sembra anche strettamente correlato alla teoria esistenziale dei reali, che di nuovo non è noto per essere in NP.

Quindi la mia domanda: questo problema è noto per essere in NP? E se è così, qualcuno potrebbe indicarmi nella giusta direzione per quanto riguarda la prova.

---

.

[1] Pascal Koiran, Nullstellensatz di Hilbert è nella gerarchia polinomiale, Journal of Complexity 12 (1996), n. 4, PP. 273-286.

Answer 1

Questo problema (solitamente chiamato quad) è infatti Completa per la teoria esistenziale dei Reali, e quindi mostrare l'adesione NP sarebbe un risultato fantastico e inaspettato.Sembra che Arora e Barak intendessero solo chiedere una prova di durezza NP.