DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# 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

# 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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#