Выделяется решающая разрешимость систем квадратичных уравнений с целочисленными коэффициентами над реалами в NP?
-
29-09-2020 - |
Вопрос
В книге «Вычислительная сложность» от ARORA и BARAK следующий вопрос (упражнение 2.20.):
Позвольте RealCaDeQ быть языком всех удовлетворенных наборов квадратичных уравнений по реальным переменным. Покажите, что RealquadeQ NP-Class.
Я знаю, как показать NP-твердость, но я застрял, когда речь идет о доказании, что эта проблема в NP, в частности, как показать, что мы можем описать решение с использованием многочлена числа битов.
Я сделал некоторые исследования и узнал, что над комплексными числами он остается открытым вопросом, если проблема в NP [1]. Это также похоже, связано с экзистенциальной теорией реалов, которые снова не известны в NP.
Таким образом, мой вопрос: это проблема известна в NP? И если да, может ли кто-нибудь указать мне в правильном направлении относительно доказательства.
[1] Паскаль Койран, Nullstellensatz Hilbert находится в полиномиальной иерархии, журнал сложности 12 (1996), нет. 4, с. 273-286.
Решение
Эта проблема (обычно называемая Quad) на самом деле полный для экзистенциальной теории реалов, и, таким образом, показывает, что NP-членство будет фантастическим и неожиданным результатом.Похоже, арора и Барак предназначались только для доказательства доказательства NP-твердости.