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$. 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

  • 2
    $\begingroup$ 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? $\endgroup$ Mar 22 '16 at 22:51
  • $\begingroup$ 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. $\endgroup$
    – maomao
    Mar 22 '16 at 23:09
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 22 '16 at 23:43
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 23 '16 at 12:28
  • 1
    $\begingroup$ I took the liberty to fix the inconsistencies in the question. $\endgroup$ Mar 23 '16 at 14:02

That problem is strongly NP-hard by reduction from 3-SAT:

Each ai is 0, each bi is 1, each negative literal is represented by its propositional variable,
each positive literal is represented by 1 minus that, each clause is represented by the product
of the representations of its literals, and f is the sum of the representations of the clauses.

I don't have any evidence regarding possible ∃ℝ-completeness or membership in NP.


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.