NP의 실제에서 정수 계수와의 2 차 방정식의 시스템의 솔프 성을 결정하고 있습니까?

Question

ARORA와 BARAK의 책의 '계산 복잡성'에서 다음 질문은 (연습 2.20) :

realquadeq가 실제 변수를 통해 모든 만족스러운 2 차 방정식 세트의 언어가되도록하십시오. RealQuadeq이 NP 완료임을 보여줍니다.

NP 경도를 보여주는 방법을 알고 있지만,이 문제가 NP에있는 것임을 증명할 때는 멈추고 있으며, 특히 우리가 다항식 수의 다항식 수를 사용하여 솔루션을 설명 할 수 있는지 보여주는 방법을 보여줍니다. 나는 연구를했고, 복소수의 숫자를 넘어서서, 문제가 NP [1]에 있다면 열려있는 질문이 남아있다. 또한 실제로의 실존 이론과 밀접하게 관련되어 있으며, 다시는 NP에있는 것으로 알려지지 않은 것으로 알려져 있지 않습니다.

이렇게 질문 :이 문제는 NP에있는 것으로 알려져 있습니까? 그렇다면 누군가가 증거와 관련하여 올바른 방향으로 나를 지적 할 수 있습니다.

---

[1] Pascal Koiran, Hilbert의 NullStellensatz는 다항식 계층 구조, 복잡성 저널 12 (1996), 아니오. 4, pp. 273-286.

Answer 1

이 문제 (일반적으로 쿼드라고 함)는 실제로 실존 이론에 대해 완전한 에 있습니다. 따라서 NP 멤버쉽이 환상적이고 예기치 않은 결과가 될 것입니다.ARORA와 BARAK은 NP 경도의 증명을 요구할만한 것으로 보입니다.