<p>Given a multivariate <strong>cubic</strong> equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge_i x_i\in[a_i, b_i]$ where $a_i, b_i$ are constant integers, the problem is to check whether $f$ has a zero in $B$. </p>

<p>What’s the complexity of this problem?</p>

<p>Obviously, it is in PSPACE; more precisely, it is a special case of the existential theory of the reals, hence it is in the class <a href="https://en.wikipedia.org/wiki/Existential_theory_of_the_reals" rel="nofollow noreferrer">$\exists\mathbb R$</a>. A related problem (denoted here as 4FEAS), viz. to check whether a <strong>quartic</strong> equation with integer coefficients (even without constraints in $B$) has a real zero is $\exists\mathbb R$-complete. Likewise, checking whether a <em>set</em> of quadratic (or cubic) equations has a common zero is $\exists\mathbb R$-complete. On the other hand, if one drops the constraint of $B$, a zero exists trivially if the cubic equation is nondegenerate. Hence, an obvious question is, can we reduce 4FEAS to the current problem?</p>

<p>A variant of 4FEAS with real coefficients is $\mathrm{NP}_\mathbb R$-complete in the Blum–Shub–Smale model, but this question is about the Boolean Turing model, not BSS.</p>

<p>A related question is here: <a href="https://cstheory.stackexchange.com/questions/34202">Checking whether two quadratic equations have a common zero</a></p>

CC BY-SA 3.0
2016-03-22T22:51:21.157Z
It's co-semidecidable, unless you are assuming that testing reals for zero is decidable or some such. What model are you working in? BSS?
Andrej Bauer
CC BY-SA 3.0
2016-03-22T23:09:25.917Z
I am a bit confused. Clearly you can reduce the problem to the existential theory of reals, and invoke Tarski's theorem to obtain PSPACE membership.
maomao
CC BY-SA 3.0
2016-03-22T23:43:37.563Z
But if the coefficients of the polynomial are arbitrary reals and so are the endpoints of the intervals, how do you apply Tarski's theory? Are you assuming that the coffecients and the endpoints are algebraic numbers? I think it would just help if you were a bit more precise about the exact assumptions you're placing on the problem.
Andrej Bauer
CC BY-SA 3.0
2016-03-22T23:53:00.520Z
oops, yes. My apology for the confusion!
maomao
CC BY-SA 3.0
2016-03-23T09:21:01.150Z
But the NP_R-complete problem is still with real coefficients, right? Are you considering some kind of BSS-to-binary cross-model reductions here?
Emil Jeřábek
CC BY-SA 3.0
2016-03-23T12:14:51.043Z
@EmilJeřábek, well here I just mentioned the hardness of solving quartic equations, but I do not really consider the BSS model. I assume the Turing model, and 4FES addresses only quartic equations with integer coefficients.
maomao
CC BY-SA 3.0
2016-03-23T12:28:16.427Z
The standard definition of 4FEAS is with real coefficints. If you want to have it with integer coefficients, you have to say so, and more importantly, the problem is no longer NP_R complete, so the formulation does not make sense. You can't use the same name for two distinct problems in one sentence. Also, it's 4FEAS (short for "feasibility"), not 4FES.
Emil Jeřábek
CC BY-SA 3.0
2016-03-23T14:02:01.523Z
I took the liberty to fix the inconsistencies in the question.
Emil Jeřábek
CC BY-SA 3.0
2016-03-23T16:37:12.887Z
Many thanks, and my apology for the confusion.
maomao
<cc.complexity-theory><computing-over-reals>
Zero of a multivariate cubic equation
maomao
# Zero of a multivariate cubic equation

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

Given a multivariate **cubic** equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge\_i x\_i\in[a\_i, b\_i]$ where $a\_i, b\_i$ are constant integers, the problem is to check whether $f$ has a zero in $B$.

What’s the complexity of this problem?

Obviously, it is in PSPACE; more precisely, it is a special case of the existential theory of the reals, hence it is in the class [$\exists\mathbb R$](https://en.wikipedia.org/wiki/Existential_theory_of_the_reals). A related problem (denoted here as 4FEAS), viz. to check whether a **quartic** equation with integer coefficients (even without constraints in $B$) has a real zero is $\exists\mathbb R$-complete. Likewise, checking whether a *set* of quadratic (or cubic) equations has a common zero is $\exists\mathbb R$-complete. On the other hand, if one drops the constraint of $B$, a zero exists trivially if the cubic equation is nondegenerate. Hence, an obvious question is, can we reduce 4FEAS to the current problem?

A variant of 4FEAS with real coefficients is $\mathrm{NP}\_\mathbb R$-complete in the Blum–Shub–Smale model, but this question is about the Boolean Turing model, not BSS.

A related question is here: [Checking whether two quadratic equations have a common zero](https://cstheory.stackexchange.com/questions/34202)

**Tags:** cc.complexity-theory, computing-over-reals

> **Comments:**
> **username_1**: It's co-semidecidable, unless you are assuming that testing reals for zero is decidable or some such. What model are you working in? BSS?  
> **username_0**: I am a bit confused. Clearly you can reduce the problem to the existential theory of reals, and invoke Tarski's theorem to obtain PSPACE membership.  
> **username_1**: But if the coefficients of the polynomial are arbitrary reals and so are the endpoints of the intervals, how do you apply Tarski's theory? Are you assuming that the coffecients and the endpoints are algebraic numbers? I think it would just help if you were a bit more precise about the exact assumptions you're placing on the problem.  
> **username_0**: oops, yes. My apology for the confusion!  
> **username_2**: But the NP_R-complete problem is still with real coefficients, right? Are you considering some kind of BSS-to-binary cross-model reductions here?  
> **username_0**: @EmilJeřábek, well here I just mentioned the hardness of solving quartic equations, but I do not really consider the BSS model. I assume the Turing model, and 4FES addresses only quartic equations with integer coefficients.  
> **username_2**: The standard definition of 4FEAS is with real coefficints. If you want to have it with integer coefficients, you have to say so, and more importantly, the problem is no longer NP_R complete, so the formulation does not make sense. You can't use the same name for two distinct problems in one sentence. Also, it's 4FEAS (short for "feasibility"), not 4FES.  
> **username_2**: I took the liberty to fix the inconsistencies in the question.  
> **username_0**: Many thanks, and my apology for the confusion.  

---

## 0 answers

