Complexity for partial computable functions over computable Polish spaces

Margarita Korovina, Oleg Kudinov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

4 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)429-447
Число страниц19
ЖурналMathematical Structures in Computer Science
Том28
Номер выпуска3
DOI
СостояниеОпубликовано - 1 мар 2018

Fingerprint Подробные сведения о темах исследования «Complexity for partial computable functions over computable Polish spaces». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать