Complexity for Partial Computable Functions over Computable Perfect Polish Spaces

Margarita Korovina

(A.P. Ershov Institute of Informatics Systems, Novosibirsk)

In the framework of effectively enumerable topological spaces we introduce the notion of a partial computable function. We show that the class of partial computable functions is closed under composition and the real-valued partial computable functions defined on a computable perfect Polish spaces have a principal computable numbering. With respect to the principal computable numbering of the real-valued partial computable functions we investigate complexity of important problems such as totality and root existence. It turns out that that for some problems the corresponding complexity does not depend on the choice of Polish space while for other ones the corresponding choice plays a crucial role.

Wednesday 20th January 2016, 15:00
Robert Recorde Room
Department of Computer Science