2
$\begingroup$

In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.):

Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real variables. Show that REALQUADEQ is NP-complete.

I know how to show NP-hardness, but I'm stuck when it comes to proving that this problem is in NP, in particular how to show that we can describe a solution using a polynomial number of bits.

I did some research and found out that over the complex numbers, it remains an open question if the problem is in NP [1]. It also seems closely related to the existential theory of the reals, which again is not known to be in NP.

Thus my question: Is this problem known to be in NP? And if so, could somebody point me in the right direction regarding the proof.


[1] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.

$\endgroup$
1
$\begingroup$

This problem (usually called QUAD) is in fact complete for the existential theory of the reals, and thus showing NP-membership would be a fantastic and unexpected result. It seems that Arora and Barak intended only to ask for a proof of NP-hardness.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I came to the same conclusion in the past days, thanks for the confirmation. Indeed, it seems to be a mistake in the book. In section 2.7.4. (where they reference Exercise 2.20) they call the problem NP-complete as well and write regarding membership in NP: "If a solution exists, then that solution serves as a certificate to this effect (of course, we have to show that the solution can be described using a polynomial number of bits, which we omit)." I will inform the authors about this error to avoid further confusion in the future. $\endgroup$ – mwien Jun 22 at 18:51
  • $\begingroup$ There seem to be some inconsistency there as well, since in the next line Hilbert’s Nullstellensatz is mentioned. However Hilbert’s Nullstellensatz does not hold over the reals. $\endgroup$ – Kristoffer Arnsfelt Hansen Jun 22 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.