Given two quadratic equations (with integer coefficients):

$x^T A_1 x+ b^T_1 x + c_1=0$ and $x^T A_2 x+ b^T_2 x + c_2=0$

The problem is to decide whether they have a common zero. Here $x$ is a vector of real numbers, i.e., we are looking for real solutions.

Q: what is the complexity of this problem?

What we know is that checking whether a family of quadratic equations has a common zero is $\exists R$-complete. However, the current question restricts the family size to be 2. A natural question arises: is this problem simpler, or remains to be $\exists R$-complete?

A related question is here: Zero of a multivariate cubic equation

  • 2
    $\begingroup$ I'm guessing from the context that the $x$ is meant to be a vector of reals? $\endgroup$ Mar 31 '16 at 8:26
  • $\begingroup$ $x$ is a vector otherwise the problem would be a bit trivial. $\endgroup$
    – maomao
    Mar 31 '16 at 11:21
  • 3
    $\begingroup$ Is x a vector of reals? ​ (as opposed to, say, rationals or complex numbers) ​ ​ ​ ​ $\endgroup$
    – user6973
    Mar 31 '16 at 12:10
  • $\begingroup$ it is a convention that we are looking for real solutions. $\endgroup$
    – maomao
    Mar 31 '16 at 13:00
  • 1
    $\begingroup$ Are you aware of any proof that your problem is NP-hard? ​ ​ $\endgroup$
    – user6973
    Mar 31 '16 at 21:28

Your Answer

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

Browse other questions tagged or ask your own question.