On the topology of algorithms. I
type: Item
instance of: scholarly article
title: On the topology of algorithms. I
zbMATH Open document ID: 0639.68042
DOI: 10.1016/0885-064X(87)90021-5
published in: Journal of Complexity
publication date: 1987-01-01T00:00:00Z
review text: The author considers the following problem: Poly(d): Given a complex polynomial f of degree d and with leading coefficient 1, find all the roots of f within \(\epsilon >0\). He defines the topological complexity of a problem as the minimum of the numbers of branching nodes of the computation trees describing the algorithms which solve that problem. The following result is derived in this paper: There exists in each dimension d an \(\epsilon (d)>0\) such that for all \(\epsilon <\epsilon (d)\) the topological complexity of the problem Poly(d) is greater than \((\log_ 2 d)^{2/3}.\) The proof uses techniques of algebraic topology. As a first step, it is shown that the topological complexity of Poly(d) is greater or equal the covering number of \(\pi\) : \({\mathbb{C}}^ d-\Delta \to {\mathcal P}_ d- \Sigma\), where \({\mathcal P}_ d\) is the space of all complex polynomials of degree d with leading coefficient fractional cascading, a new searching technique which has been described in a companion paper (see the preceding review). The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 57M10
Mathematics Subject Classification ID: 55N45
Mathematics Subject Classification ID: 55M30
zbMATH DE Number: 4043247
zbMATH Keywords: cohomology ring of braid group
zbMATH Keywords: topological complexity
zbMATH Keywords: branching nodes
zbMATH Keywords: computation trees
zbMATH Keywords: algorithms
zbMATH Keywords: covering number
zbMATH Keywords: fractional cascading
zbMATH Keywords: range search
author: Stephen Smale
MaRDI profile type: Publication
cites work: Q5566960
cites work: Q4403463
cites work: The homology of iterated loop spaces
cites work: Configuration Spaces.
cites work: Cohomologies of the group COS mod 2
cites work: Q5599554
cites work: Q3496299
cites work: Q5335878
cites work: Q4124327
cites work: Q4064159
cites work: Q5522742
cites work: Lower bounds for algebraic decision trees
full work available at URL: 0885-064x(87)90021-5
OpenAlex ID: W2055359591
description: scientific article; zbMATH DE number 4043247