Cohomology of braid groups and complexity. (English) Zbl 0803.55005
Hirsch, M. W. (ed.) et al., From topology to computation: Proceedings of the Smalefest. Papers presented at the conference “From topology to computation: Unity and diversity in the mathematical sciences” held at the University of California at Berkeley, USA, August 5-9, 1990 in honor of Stephen Smale’s 60th birthday. New York: Springer-Verlag. 359-367 (1993).
An algorithm can be viewed as a directed graph having four sorts of nodes: (1) one input node, (2) computational nodes, (3) branching nodes (IF-statements, having one input and two outputs) and (4) several output nodes. The topological complexity of an algorithm is defined to be the number of branching nodes. The topological complexity of a problem is the minimum over the topological complexities of all algorithms which solve the problem.
Let \(\tau (d,\varepsilon)\) be the topological complexity of finding all roots of a polynomial \(z^ d+ a_{d-1} z^{d-1}+ \dots +a_ 0\) with error less than \(\varepsilon\). The author outlines Smale’s approach to estimating \(\tau (d,\varepsilon)\). Let \(B^ d\) be the space of all polynomials of the above form, let \(\Sigma \subset B^ d\) be the subset of polynomials having multiple roots and let \(f_ d: M^ d \to B^ d \setminus \Sigma\) be the \(d\)!-fold covering such that the fibre over a polynomial consists of all ordered \(d\)-tuples of roots. Then, according to Smale, one has (assuming \(\varepsilon\) to be small enough): \(\tau (d,\varepsilon) \geq g(f_ d) -1\). Here \(g(f_ d)\) is the Schwarz genus of the map \(f_ d\), i.e. the minimum number of open sets which cover the base space and such that over each of the open sets the covering is trivial.
The base space \(B^ d \setminus \Sigma\) is an Eilenberg-MacLane-space of type \(K( Br(d), 1)\), where \(Br(d)\) is the braid group on \(d\) strings. The covering \(f_ d\) has a classifying map \(cl: K(Br(d), 1)\to K(\Sigma_ d, 1)\), where \(\Sigma_ d\) is the symmetric group. For any \(\Sigma_ d\) module \(A\) there are induced maps \(cl^ i: H^ i (\Sigma_ d; A)\to H^ i (Br(d); A)\) and the homological \(A\)-genus of \(f_ d\) is the smallest \(j\) such that \(cl^ i\) is the trivial homomorphism for all \(i\geq j\). This is a lower bound for the Schwarz genus. Using this the author gives the following estimate: \(d- D_ p (d)\leq \tau(d, \varepsilon)\leq d-1\), where \(\varepsilon\) is small enough, \(p\) is any prime and \(D_ p (d)\) is the sum of digits in the \(p\)-adic expansion of \(d\).
The author then outlines a generalization of this methods and results to the study of algorithms solving systems of polynomial equations, but the results are too complicated to be presented here.
For the entire collection see [Zbl 0779.00016].
Let \(\tau (d,\varepsilon)\) be the topological complexity of finding all roots of a polynomial \(z^ d+ a_{d-1} z^{d-1}+ \dots +a_ 0\) with error less than \(\varepsilon\). The author outlines Smale’s approach to estimating \(\tau (d,\varepsilon)\). Let \(B^ d\) be the space of all polynomials of the above form, let \(\Sigma \subset B^ d\) be the subset of polynomials having multiple roots and let \(f_ d: M^ d \to B^ d \setminus \Sigma\) be the \(d\)!-fold covering such that the fibre over a polynomial consists of all ordered \(d\)-tuples of roots. Then, according to Smale, one has (assuming \(\varepsilon\) to be small enough): \(\tau (d,\varepsilon) \geq g(f_ d) -1\). Here \(g(f_ d)\) is the Schwarz genus of the map \(f_ d\), i.e. the minimum number of open sets which cover the base space and such that over each of the open sets the covering is trivial.
The base space \(B^ d \setminus \Sigma\) is an Eilenberg-MacLane-space of type \(K( Br(d), 1)\), where \(Br(d)\) is the braid group on \(d\) strings. The covering \(f_ d\) has a classifying map \(cl: K(Br(d), 1)\to K(\Sigma_ d, 1)\), where \(\Sigma_ d\) is the symmetric group. For any \(\Sigma_ d\) module \(A\) there are induced maps \(cl^ i: H^ i (\Sigma_ d; A)\to H^ i (Br(d); A)\) and the homological \(A\)-genus of \(f_ d\) is the smallest \(j\) such that \(cl^ i\) is the trivial homomorphism for all \(i\geq j\). This is a lower bound for the Schwarz genus. Using this the author gives the following estimate: \(d- D_ p (d)\leq \tau(d, \varepsilon)\leq d-1\), where \(\varepsilon\) is small enough, \(p\) is any prime and \(D_ p (d)\) is the sum of digits in the \(p\)-adic expansion of \(d\).
The author then outlines a generalization of this methods and results to the study of algorithms solving systems of polynomial equations, but the results are too complicated to be presented here.
For the entire collection see [Zbl 0779.00016].
Reviewer: H.M.Unsöld (Berlin)
MSC:
| 55R99 | Fiber spaces and bundles in algebraic topology |
| 68Q25 | Analysis of algorithms and problem complexity |
| 20F36 | Braid groups; Artin groups |
