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

$\endgroup$
5
  • 4
    $\begingroup$ This is as hard as solving general polynomial equations. $\endgroup$ May 28, 2020 at 11:49
  • $\begingroup$ When you say "solve", are you asking for a numerical solution, or what? $\endgroup$ 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
    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$ May 28, 2020 at 16:50
  • $\begingroup$ In numerical practice, I would use something like Newton's method or homotopy continuation. $\endgroup$ May 28, 2020 at 16:51

1 Answer 1

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.