Sta decidendo la solvibilità dei sistemi di equazioni quadratiche con i coefficienti interi sui reali in NP?
-
29-09-2020 - |
Domanda
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.
Soluzione
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.