Complexity for partial computable functions over computable Polish spaces

Margarita Korovina, Oleg Kudinov

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

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 Polish space 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 verification. It turns out that for some problems the corresponding complexity does not depend on the choice of a computable Polish space, whereas for other ones the corresponding choice plays a crucial role.

Original languageEnglish
Pages (from-to)429-447
Number of pages19
JournalMathematical Structures in Computer Science
Volume28
Issue number3
DOIs
Publication statusPublished - 1 Mar 2018

Fingerprint

Dive into the research topics of 'Complexity for partial computable functions over computable Polish spaces'. Together they form a unique fingerprint.

Cite this