Topological Complexity of Algorithms
Abstract
The research was directed toward understanding methods for calculating complexity of algorithms in non-classical sense. Topological complexity measures the necessity of branching in any possible algorithm for solving given problem. Particular problems which I considered are solving polynomial equations of special type (i.e. with several apriori vanishing coefficients). The difficulty is in the lack at the present time detailed information on geometry and topology of discriminants of the space of polynomial equations of the type in question. I was able to find the degrees of these discriminants and resolved questions of irreducibility. Topological complexity was found completely for trinomial equations. Major steps was made toward investigating of algorithms for solving systems of 2 polynomial equations with 2 unknowns. I essentially calculated the fundamental group of the space of such system obtaining close relations to the Artin's braid group. Preliminary investigation was made in the meaning of topological complexity of solving differential equations. (JHD)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 12, 1990
- Accession Number
- ADA220274
Entities
People
- A. Libgober
Organizations
- University of Illinois at Chicago