Выделяется решающая разрешимость систем квадратичных уравнений с целочисленными коэффициентами над реалами в NP?

Question

В книге «Вычислительная сложность» от ARORA и BARAK следующий вопрос (упражнение 2.20.):

Позвольте RealCaDeQ быть языком всех удовлетворенных наборов квадратичных уравнений по реальным переменным. Покажите, что RealquadeQ NP-Class.

Я знаю, как показать NP-твердость, но я застрял, когда речь идет о доказании, что эта проблема в NP, в частности, как показать, что мы можем описать решение с использованием многочлена числа битов.

Я сделал некоторые исследования и узнал, что над комплексными числами он остается открытым вопросом, если проблема в NP [1]. Это также похоже, связано с экзистенциальной теорией реалов, которые снова не известны в NP.

Таким образом, мой вопрос: это проблема известна в NP? И если да, может ли кто-нибудь указать мне в правильном направлении относительно доказательства.

---

[1] Паскаль Койран, Nullstellensatz Hilbert находится в полиномиальной иерархии, журнал сложности 12 (1996), нет. 4, с. 273-286.

Answer 1

Эта проблема (обычно называемая Quad) на самом деле полный для экзистенциальной теории реалов, и, таким образом, показывает, что NP-членство будет фантастическим и неожиданным результатом.Похоже, арора и Барак предназначались только для доказательства доказательства NP-твердости.