Journal of Complexity · 1996 · 12 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationTopologyAlgorithm AnalysisComplexity TheoryComputational ComplexityComputational Complexity ClassesComputational TopologyComplexityComplexity Of Numerical Algorithms
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.
8
Science · 1989 · 861 citations
Edward W. Packel, J. F. Traub · Nature · 1987 · 504 citations
On the topology of algorithms, I
Steve Smale · Journal of Complexity · 1987 · 152 citations