Solving a nonlinear equation system: is there a general result on complexity? [closed]

Question

If there is a system of nonlinear equations and all variables are unbounded real numbers and the functions are continuous, is there a general result on the complexity of solving it? More specifically, can a statement be made about how the computational time to numerically solve the system increases with the number of variables and equations? I am particularly looking for a literature reference for such a statement.

Answer 1

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

EDIT: ... and even then, depending on the precise formulation of the problem, it can be impossible. Consider the following family of functions. Given Turing machines $T_0$ and $T_1$ (including specified inputs), let $$f(x) = \sum_{n=1}^\infty \left(a_n x^{n} + b_n (x-1)^{n}\right)$$ where

1. If $T_0$ halts in exactly $n$ steps and $T_1$ has not halted by $n$ steps, $a_n = 1/n!$ and $ b_n = 0$.
2. If $T_1$ halts in exactly $n$ steps and $T_0$ has not halted by $n$ steps, $a_n = 0$ and $b_n = 1/n!$.
3. Otherwise $a_n = b_n = 0$.

If $T_0$ halts before $T_1$, $f(x)=0$ has the unique solution $x=0$; if $T_1$ halts before $T_0$, it has the unique solution $x=1$; if neither halts, or if they halt at the same step, all $x$ are solutions.

Note that $f(x)$ is a perfectly nice function, in fact a polynomial. The value of $f$ or any of its derivatives at a given point can be approximated with arbitrary precision by simulating sufficiently many steps of the Turing machines. But since there is no algorithm to determine whether a Turing machine halts on given input, there is no algorithm to find (or approximate) a solution to $f(x)=0$.