What is the complexity of global solution of a nonlinear system?

Question

Consider an $n$-dimensional system $F_j(x_1, \ldots, x_n) = 0, j = 1, \ldots, n$. The functions $F_j$ can be considered as monotonic w.r.t. all $x_i$. What is the complexity of the problem of finding all roots of the system? Is it $O(2^n)$ or it may be enhanced as in a linear case?

Answer 1

In the worst case, $F_j=0$ for all $j$, and then there are at least $2^n$ roots. Obviously any method to print all roots must take time at least equal to the number of roots, so this proves that the worst-case running time of any method must be at least $\Omega(2^n)$. In other words, there is no hope for a method whose worst-case running time is better.

In general, even with some restrictions, you still shouldn't hope for anything better, as this is at least as hard as any NP-hard problem. Monotonicity doesn't help. For instance, vertex cover and other NP-hard problems can be represented as such a monotonic system of equations.