Let $N=\{1,2,\ldots,n\}$. Suppose we are given $n$ equations, with each equation taking the form $\sum_{A\subseteq N}\left(c_A \prod_{i\in A}x_i \right) = 0$, where each $c_A$ is a real number constant. (So each equation contains at most $2^n$ terms.) An example for $n=3$ is:

$$2x_1x_2x_3 - 4x_1x_2+5x_3+2=0$$

$$7x_1x_3 - 6x_2-4=0$$

$$-x_1x_2x_3 + x_1 - 2x_2 +9 = 0$$

We want to find a solution $(x_i)_{i\in A}$ such that $0\leq x_i\leq 1$ for all $i$ (assuming we know such a solution exists).

Is there an algorithm that solves this in time bounded in $n$?

  • 4
    $\begingroup$ This is as hard as solving general polynomial equations. $\endgroup$ – Emil Jeřábek May 28 at 11:49
  • $\begingroup$ When you say "solve", are you asking for a numerical solution, or what? $\endgroup$ – Zach Teitler May 28 at 16:15
  • $\begingroup$ @ZachTeitler Can we possibly solve this exactly (like we can do for linear equations), or is there some reason why this is impossible? $\endgroup$ – Alexi May 28 at 16:27
  • 1
    $\begingroup$ @Alexi Exactly, no. With the trick in Vladimir Dotsenko's answer you can easily write a degree-5 polynomial equation in this form, by adding extra variables for $x^2, x^3, x^4$. Evil Abel foils our plans again. $\endgroup$ – Federico Poloni May 28 at 16:50
  • $\begingroup$ In numerical practice, I would use something like Newton's method or homotopy continuation. $\endgroup$ – Federico Poloni May 28 at 16:51

Multilinear equations are hardly easier than general equations. For instance, the multilinear equations $$ \begin{cases} x_0-x_1=0,\\ x_0x_1-x_2=0,\\ x_0x_2-x_3=0,\\ \ldots\\ x_0x_{n-1}-x_n=0 \end{cases} $$ simply tell you that $x_k=x_0^k$ for all $k=1,\ldots,n$. Using this, it is very easy to replace any system of polynomial equations by a system of multilinear ones, so I assume that the most standard method (Gröbner bases) would be the main tool to use.

| cite | improve this answer | |

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.