Topological Complexity of Algorithms.

摘要

The research was directed toward understanding methods for calculating complexity of algorithms in a non-classical sense. Topological complexity measures the necessity of branching in any possible algorithm for solving a given problem. Particular problems which I considered are solving polynomial equations of a special type (i.e. with several apriori vanishing coefficients). The difficulty is in the lack of 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 were taken toward investigating algorithms for solving systems of 2 polynomial equations with 2 unknowns. I essentially calculated the fundamental group of the space of such systems obtaining close relations to the Artin's braid group. Preliminary investigation was made in the meaning of topological complexity of solving differential equations. Keywords: Topological complexity, Fundamental groups, Discriminants. (DD1473 only). (JHD)