Accession Number:

ADA220274

Title:

Topological Complexity of Algorithms

Descriptive Note:

Final rept. 16 Dec 1988-15 Dec 1989,

Corporate Author:

ILLINOIS UNIV AT CHICAGO CIRCLE DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1990-03-12

Pagination or Media Count:

2.0

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 Artins braid group. Preliminary investigation was made in the meaning of topological complexity of solving differential equations. JHD

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE