Está decidindo a solubilidade de sistemas de equações quadráticas com coeficientes inteiros sobre os reais em NP?

Question

No livro 'Complexidade Computacional' de Arora e Barak é colocada a seguinte questão (exercício 2.20.):

Seja REALQUADEQ a linguagem de todos os conjuntos satisfatíveis de equações quadráticas sobre variáveis ​​reais.Mostre que REALQUADEQ é NP-completo.

Eu sei como mostrar a dureza NP, mas não consigo provar que esse problema está em NP, em particular como mostrar que podemos descrever uma solução usando um número polinomial de bits.

Fiz algumas pesquisas e descobri que nos números complexos permanece uma questão em aberto se o problema está em NP [1].Também parece intimamente relacionado com a teoria existencial dos reais, que novamente não é conhecida por estar em NP.

Assim, minha pergunta:Este problema é conhecido por estar em NP?E se sim, alguém poderia me indicar a direção certa em relação à prova.

---

[1] Pascal Koiran, Nullstellensatz de Hilbert está na Hierarquia Polinomial, Journal of Complexity 12 (1996), no.4, pp.273–286.

Answer 1

Este problema (geralmente chamado QUAD) é na verdade completo para a teoria existencial dos reais e, portanto, mostrar a adesão ao NP seria um resultado fantástico e inesperado.Parece que Arora e Barak pretendiam apenas pedir uma prova da dureza NP.