3
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ This is as hard as solving general polynomial equations. $\endgroup$
    – Emil Jeřábek
    Commented May 28, 2020 at 11:49
  • $\begingroup$ When you say "solve", are you asking for a numerical solution, or what? $\endgroup$
    – Zach Teitler
    Commented May 28, 2020 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
    Commented May 28, 2020 at 16:27
  • 2
    $\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
    Commented May 28, 2020 at 16:50
  • $\begingroup$ In numerical practice, I would use something like Newton's method or homotopy continuation. $\endgroup$
    – Federico Poloni
    Commented May 28, 2020 at 16:51

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .