Skip to main content
4 of 6
deleted 86 characters in body
Alexi
  • 239
  • 2
  • 10

Solving multilinear equations

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

Alexi
  • 239
  • 2
  • 10