Está decidindo a solubilidade de sistemas de equações quadráticas com coeficientes inteiros sobre os reais em NP?
-
29-09-2020 - |
Pergunta
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.
Solução
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.