NPの実数にわたる整数係数を持つ2次方程式のシステムの解決率を決定していますか？

Question

ARORAとBARAKによる「計算複雑さ」では、次の質問が提起されている（演習2.20）。

RealQuadeQを実数変数にわたる全ての満足度の一連の二次方程式の言語にすることができます。 REALQUADEQがNP完成であることを示します。

私はNP硬さを示す方法を知っていますが、この問題がNPにあることを証明することになると、特に多項式のビット数を使用して解決策を説明できることを証明するようになりました。

私はいくつかの研究をして、複素数を超えて、問題がNP [1]にある場合は開いた質問のままです。それはまた、実際の実態理論と密接に関連しているように思われます。これは再びNPにあることが知られていません。

私の質問：この問題はNPにあることが知られていますか？そうであれば、誰かが証明に関して正しい方向に私を指していることができます。

---

[1] Pascal Koiran、HilbertのNullstellensatzは多項式階層、複雑さのジャーナル12（1996）、No. 4、pp.273-286。

Answer 1

この問題（通常はクワッドと呼ばれる）は、実際の実質的な理論のための完全であり、したがってNPメンバーシップを示すことは素晴らしくて予想外の結果になるでしょう。アロラとバラックは、NP硬度の証明を求めることだけを意図しているようです。