Complexity for partial computable functions over computable Polish spaces | Sciact - Система учета научной деятельности ИМ СО РАН

Complexity for partial computable functions over computable Polish spaces Научная публикация

Журнал

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

Вых. Данные

Год: 2018, Том: 28, Номер: 3, Страницы: 429-447 Страниц : 19 DOI: 10.1017/S0960129516000438

Авторы

Korovina M. ¹ , Kudinov O. ²

Организации

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

БД	Цитирований
Scopus	4
OpenAlex	3
Web of science	3