Complexity for partial computable functions over computable Polish spaces

Complexity for partial computable functions over computable Polish spaces Full article

Journal

Mathematical Structures in Computer Science
ISSN: 0960-1295 , E-ISSN: 1469-8072

Output data

Year: 2018, Volume: 28, Number: 3, Pages: 429-447 Pages count : 19 DOI: 10.1017/S0960129516000438

Authors

Korovina M. ¹ , Kudinov O. ²

Affiliations

1	A.P. Ershov Institute of Informatics Systems, NSU, Novosibirsk, Russian Federation
2	Sobolev Institute of Mathematics, NSU, Novosibirsk, Russian Federation

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. © 2016 Cambridge University Press.

Korovina M. , Kudinov O.
Complexity for partial computable functions over computable Polish spaces
Mathematical Structures in Computer Science. 2018. V.28. N3. P.429-447. DOI: 10.1017/S0960129516000438 WOS Scopus OpenAlex

Web of science:	WOS:000426961400006
Scopus:	2-s2.0-85006263328
OpenAlex:	W2565599026

DB	Citing
Scopus	4
OpenAlex	3
Web of science	3