是在NP中的真实系数与整数系数的二次方程系统的可解性?
-
29-09-2020 - |
题
在arora和barak的书“计算复杂性”下面提出了以下问题(练习2.20。):
让RealQuadeq是真实变量上所有可满足二次方程集的语言。显示RealQuadeq是NP-Cleante。
我知道如何展示NP硬度,但是当谈到证明这个问题是在NP中,特别是如何表明我们可以使用多项式的比特数来描述一个解决方案。
我做了一些研究,发现了在复杂的数字上,如果问题在NP [1]中,它仍然是一个开放的问题。它看起来与真实的存在理论密切相关,再次被称为NP。
因此我的问题:是否知道这个问题是在NP中?如果是这样,有人可以指出关于证明的正确方向。
[1] Pascal Koiran,希尔伯特的Nullstellensatz在多项式层次中,复杂性12(1996),没有。 4,pp。273-286。
解决方案
这个问题(通常称为Quad)实际上完成了真实存在理论的,因此显示NP-隶属是一个很棒和意外的结果。似乎arora和barak只是为了询问NP硬度的证据。
不隶属于 cs.stackexchange