1
$\begingroup$

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 ?
$\endgroup$
  • 5
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Mar 13 '16 at 11:29
  • $\begingroup$ @EmilJeřábek: Sounds like a great answer to me :). $\endgroup$ – Joshua Grochow Mar 14 '16 at 4:55
  • $\begingroup$ @JoshuaGrochow: All right, made it an answer. $\endgroup$ – Emil Jeřábek Mar 15 '16 at 16:20
  • $\begingroup$ @EmilJeřábek: I'm glad you did, as I learned something new from your more detailed answer - thanks! $\endgroup$ – Joshua Grochow Mar 15 '16 at 17:49
6
$\begingroup$

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.

$\endgroup$

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.