<p>The question seems to be based on false premises, so let me try to deconfuse it.</p>

<ul>
<li><p>Solvability of systems of polynomial equations with integer coefficients is NP-hard over any fixed field (or integral domain). For instance, it is straightforward to reduce the satisfiability of a 3-CNF $\phi(x_1,\dots,x_k)$ to the solvability of a polynomial system including $\{x_i^2-x_i:i=1,\dots,k\}$ and a bunch of polynomials translating each 3-clause.</p></li>
<li><p>Solvability of general polynomial systems with integer (or rational) coefficients is polynomially reducible to solvability of systems of multilinear degree-$2$ polynomials with coefficients in $\{-1,0,1\}$ and at most $3$ nonzero monomials each. To see this, express each polynomial by an arithmetical circuit (aka straightline program) using operations $+$, $\cdot$, variables, and constants $0,1,-1$. Introduce a new variable for each node in the circuit, and take the set of polynomials describing the value of each node in terms of its inputs.</p></li>
<li><p>The multivariate polynomial ring $K[x_1,\dots,x_k]$ (for a field $K$) is indeed a GCD domain, but for $k\ge2$ it is not a Bézout domain, hence the gcd’s do not behave the way you think they do. For example, the polynomials $x_1$ and $x_2$ have a common root $(0,0)$, even though $\gcd(x_1,x_2)=1$.</p></li>
</ul>

<p>Thus, your problem is NP-hard, and as such it has no known polynomial-time algorithm (deterministic or randomized). Under plausible assumptions, it even has no subexponential-time randomized algorithm.</p>

<p>Furthermore:</p>

<ul>
<li><p>Over a field, inequations can be replaced by equations: instead of $q(x_1,\dots,x_k)\ne0$, use $q(x_1,\dots,x_k)y=1$, where $y$ is a fresh variable.</p></li>
<li><p>Solvability of systems of polynomial equations (hence also inequations, by above) in $\mathbb C$ can be ckecked in PSPACE, due to Canny [1]. This is the best known unconditional result, but:</p></li>
<li><p>Assuming the Riemann hypothesis for Dedekind $\zeta$ functions, solvability of polynomial systems in $\mathbb C$ can be checked in the class AM, due to Koiran [2]. Moreover, we can derandomize AM to NP under plausible Nisan–Widgerson-style complexity assumptions, thus assuming both, the problem becomes NP-complete.</p></li>
</ul>

<p>[1] John Canny, <em>Some algebraic and geometric computations in PSPACE</em>, Proc. 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 460–467.</p>

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

CC BY-SA 3.0
2016-03-15T16:19:09.457Z
2016-03-15T16:19:09.457Z
Emil Jeřábek
<p>Formally, I have 2 finite sets of polynomials :</p>

<p>$P = \{p_1, p_2, p_3, ...p_m\}$ and $Q = \{q_1, q_2, q_3, ...q_n\}$, where for $1 \leq i \leq m$, and $1 \leq j \leq n$, I have $p_i, q_j \in \mathbb{C}[x_1, x_2, \ldots x_k]$ (that is these are multivariate polynomials that can admit roots with possibly complex values for each of the variables) [although the coefficients can be assumed to be over $\mathbb{Z}$ or $\mathbb{Q}$]</p>

<p>What are the most efficient (having running time polynomial in the number of variables, and number of polynomials, but not necessarily the degree) algorithms to check for existence of a solution $\bar{u} = (u_1, \ldots, u_k) \in \mathbb{C}^k$ such that $p_i(u_1, \ldots, u_k) = 0$, and $q_j(u_1, \ldots, u_k)\neq 0$, for all $1 \leq i \leq m$, and $1 \leq j \leq n$.</p>

<p>P.S: For the specific problem I am looking into, the degree (maximum sum of powers of variables in any term) does not exceed 2.That is the polynomials, are in some sense, <em>sparse</em>. </p>

<p><strong>Remark</strong></p>

<ol>
<li>The set of all such points in $\mathbb{C}^k$ is sometimes referred to as <em>constructible</em> sets, and I understand that an <em>efficient</em> algorithm for calculating GCD of multi-variate polynomials immediately yields an efficient algorithm for solving the above problem. I tried to do a (somewhat extensive) survey for relevant literature, but could not really find efficient algorithms (that run in time polynomial in the number of variables, and the number of polynomials).</li>
<li>Are there any efficient randomized algorithms ?</li>
</ol>

CC BY-SA 3.0
2016-03-13T11:29:53.693Z
Any system of polynomials is polynomially reducible to a system of degree 2 by introduction of extension variables. Thus, your problem is NP-hard, and you are not going to find a polynomial algorithm (even randomized). FWIW, inequations can be replaced by equations over any field, and solvability of polynomial systems (with rational coefficients) in $\mathbb C$ can be checked unconditionally in PSPACE, and in AM assuming the Riemann hypothesis for Dedekind $\zeta$ functions (or even in NP, under further derandomization assumptions).
Emil Jeřábek
CC BY-SA 3.0
2016-03-14T04:55:56.053Z
@EmilJeřábek: Sounds like a great answer to me :).
Joshua Grochow
CC BY-SA 3.0
2016-03-15T16:20:30.437Z
@JoshuaGrochow: All right, made it an answer.
Emil Jeřábek
CC BY-SA 3.0
2016-03-15T17:49:44.760Z
@EmilJeřábek: I'm glad you did, as I learned something new from your more detailed answer - thanks!
Joshua Grochow
<cc.complexity-theory><polynomials>
Existence of solution for a system of multi-variate polynomial equations and in-equations
Umang
# Existence of solution for a system of multi-variate polynomial equations and in-equations

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

Formally, I have 2 finite sets of polynomials :

$P = \{p\_1, p\_2, p\_3, ...p\_m\}$ and $Q = \{q\_1, q\_2, q\_3, ...q\_n\}$, where for $1 \leq i \leq m$, and $1 \leq j \leq n$, I have $p\_i, q\_j \in \mathbb{C}[x\_1, x\_2, \ldots x\_k]$ (that is these are multivariate polynomials that can admit roots with possibly complex values for each of the variables) [although the coefficients can be assumed to be over $\mathbb{Z}$ or $\mathbb{Q}$]

What are the most efficient (having running time polynomial in the number of variables, and number of polynomials, but not necessarily the degree) algorithms to check for existence of a solution $\bar{u} = (u\_1, \ldots, u\_k) \in \mathbb{C}^k$ such that $p\_i(u\_1, \ldots, u\_k) = 0$, and $q\_j(u\_1, \ldots, u\_k)\neq 0$, for all $1 \leq i \leq m$, and $1 \leq j \leq n$.

P.S: For the specific problem I am looking into, the degree (maximum sum of powers of variables in any term) does not exceed 2.That is the polynomials, are in some sense, *sparse*.

**Remark**

1. The set of all such points in $\mathbb{C}^k$ is sometimes referred to as *constructible* sets, and I understand that an *efficient* algorithm for calculating GCD of multi-variate polynomials immediately yields an efficient algorithm for solving the above problem. I tried to do a (somewhat extensive) survey for relevant literature, but could not really find efficient algorithms (that run in time polynomial in the number of variables, and the number of polynomials).
2. Are there any efficient randomized algorithms ?

**Tags:** cc.complexity-theory, polynomials
> **Comments:**
> **username_1**: Any system of polynomials is polynomially reducible to a system of degree 2 by introduction of extension variables. Thus, your problem is NP-hard, and you are not going to find a polynomial algorithm (even randomized). FWIW, inequations can be replaced by equations over any field, and solvability of polynomial systems (with rational coefficients) in $\mathbb C$ can be checked unconditionally in PSPACE, and in AM assuming the Riemann hypothesis for Dedekind $\zeta$ functions (or even in NP, under further derandomization assumptions).  
> **username_2**: @EmilJeřábek: Sounds like a great answer to me :).  
> **username_1**: @JoshuaGrochow: All right, made it an answer.  
> **username_2**: @EmilJeřábek: I'm glad you did, as I learned something new from your more detailed answer - thanks!  

---

## 1 answers

### Answer by username_1 on 2016-03-15. Score: 7 | Accepted answer

The question seems to be based on false premises, so let me try to deconfuse it.

* Solvability of systems of polynomial equations with integer coefficients is NP-hard over any fixed field (or integral domain). For instance, it is straightforward to reduce the satisfiability of a 3-CNF $\phi(x\_1,\dots,x\_k)$ to the solvability of a polynomial system including $\{x\_i^2-x\_i:i=1,\dots,k\}$ and a bunch of polynomials translating each 3-clause.
* Solvability of general polynomial systems with integer (or rational) coefficients is polynomially reducible to solvability of systems of multilinear degree-$2$ polynomials with coefficients in $\{-1,0,1\}$ and at most $3$ nonzero monomials each. To see this, express each polynomial by an arithmetical circuit (aka straightline program) using operations $+$, $\cdot$, variables, and constants $0,1,-1$. Introduce a new variable for each node in the circuit, and take the set of polynomials describing the value of each node in terms of its inputs.
* The multivariate polynomial ring $K[x\_1,\dots,x\_k]$ (for a field $K$) is indeed a GCD domain, but for $k\ge2$ it is not a Bézout domain, hence the gcd’s do not behave the way you think they do. For example, the polynomials $x\_1$ and $x\_2$ have a common root $(0,0)$, even though $\gcd(x\_1,x\_2)=1$.

Thus, your problem is NP-hard, and as such it has no known polynomial-time algorithm (deterministic or randomized). Under plausible assumptions, it even has no subexponential-time randomized algorithm.

Furthermore:

* Over a field, inequations can be replaced by equations: instead of $q(x\_1,\dots,x\_k)\ne0$, use $q(x\_1,\dots,x\_k)y=1$, where $y$ is a fresh variable.
* Solvability of systems of polynomial equations (hence also inequations, by above) in $\mathbb C$ can be ckecked in PSPACE, due to Canny [1]. This is the best known unconditional result, but:
* Assuming the Riemann hypothesis for Dedekind $\zeta$ functions, solvability of polynomial systems in $\mathbb C$ can be checked in the class AM, due to Koiran [2]. Moreover, we can derandomize AM to NP under plausible Nisan–Widgerson-style complexity assumptions, thus assuming both, the problem becomes NP-complete.

[1] John Canny, *Some algebraic and geometric computations in PSPACE*, Proc. 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 460–467.

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


---

