Title: Continuous Reducibility of Functions

Name: Peter Hertling

Affiliation:
Universitaet der Bundeswehr, Munich, Germany

Abstract:
The topological complexity of a computational problem
over the real numbers is the minimum number of tests
or comparisons that one needs to perform in order to
solve the problem. It has turned out that the topological
complexity of a problem can be very different depending
on the set of operations  which, besides comparisons,
are allowed for its solution: either only algebraic operations,
or also other operations like exp, log, absolute value,
or even all continous operations, which is the purely
topological setting.
In the purely topological setting the topological complexity
can be characterized as a degree of discontinuity as well.
Furthermore, it is closely related to the Schwarz genus.
After presenting fundamental definitions and results,
we present several examples of problems for which the
topological complexity has been investigated.
Then we consider several continuous reducibility
relation of functions on the Cantor space similar to Wadge
reducibility of subsets and show that they lead to refinements
of the topological complexity in the purely topological setting,
for problems over admissibly represented topological spaces.