<p>Given two quadratic equations (with integer coefficients):</p>

<p>$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$</p>

<p>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.</p>

<p>Q: what is the complexity of this problem?</p>

<p>What we know is that checking whether a <em>family</em> 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?</p>

<p>A related question is here: <a href="https://cstheory.stackexchange.com/questions/34139">Zero of a multivariate cubic equation</a></p>

CC BY-SA 3.0
2016-03-31T08:26:25.410Z
I'm guessing from the context that the $x$ is meant to be a vector of reals?
Emil Jeřábek
CC BY-SA 3.0
2016-03-31T11:21:17.683Z
$x$ is a vector otherwise the problem would be a bit trivial.
maomao
CC BY-SA 3.0
2016-03-31T13:00:13.707Z
it is a convention that we are looking for real solutions.
maomao
CC BY-SA 3.0
2016-04-03T00:30:37.027Z
@RickyDemer I don't know about the two equation case (or even a fixed constant). But, subset sum with n integers reduces to $n+1$ equations via the binary-enforcing $x_i(1-x_i)=0$ equations.
Austin Buchanan
<cc.complexity-theory><algebraic-complexity><quadratic>
Checking whether two quadratic equations have a common zero
maomao
# Checking whether two quadratic equations have a common zero

(Asked by: username_0 on 2016-03-30)

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](https://cstheory.stackexchange.com/questions/34139)

**Tags:** cc.complexity-theory, algebraic-complexity, quadratic

> **Comments:**
> **username_1**: I'm guessing from the context that the $x$ is meant to be a vector of reals?  
> **username_0**: $x$ is a vector otherwise the problem would be a bit trivial.  
> **username_0**: it is a convention that we are looking for real solutions.  
> **username_2**: @RickyDemer I don't know about the two equation case (or even a fixed constant). But, subset sum with n integers reduces to $n+1$ equations via the binary-enforcing $x_i(1-x_i)=0$ equations.  

---

## 0 answers

