TY - JOUR

T1 - Complexity for partial computable functions over computable Polish spaces

AU - Korovina, Margarita

AU - Kudinov, Oleg

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85006263328&partnerID=8YFLogxK

U2 - 10.1017/S0960129516000438

DO - 10.1017/S0960129516000438

M3 - Article

AN - SCOPUS:85006263328

VL - 28

SP - 429

EP - 447

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

SN - 0960-1295

IS - 3

ER -