Topological Complexity of Zero-Finding
Erich Novak, H. Woźniakowski · Journal of Complexity · 1996
The topological complexity of zero-finding is studied using a BSS machine over the reals with an information node. The topological complexity depends on the class of functions, the class of arithmetic operations, and on the error criterion. For the root error criterion the following results are established. If only Hölder operations are permitted as arithmetic operations then the topological complexity is roughly −log2ϵ and bisection is optimal. This holds even for the small class of linear functions. On the other hand, for the class of all increasing functions, if we allow the sign function or division, together with log and exp, then the topological complexity drops to zero. For the residual error criterion, results can be totally different than for the root error criterion. For example, the topological complexity can be zero for the residual error criterion, and roughly −log2ϵ for the root error criterion.