Standard

Complexity for partial computable functions over computable Polish spaces. / Korovina, Margarita; Kudinov, Oleg.

In: Mathematical Structures in Computer Science, Vol. 28, No. 3, 01.03.2018, p. 429-447.

Research output: Contribution to journal › Article › peer-review

Harvard

Korovina, M & Kudinov, O 2018, 'Complexity for partial computable functions over computable Polish spaces', Mathematical Structures in Computer Science, vol. 28, no. 3, pp. 429-447. https://doi.org/10.1017/S0960129516000438

APA

Korovina, M., & Kudinov, O. (2018). Complexity for partial computable functions over computable Polish spaces. Mathematical Structures in Computer Science, 28(3), 429-447. https://doi.org/10.1017/S0960129516000438

Vancouver

Korovina M, Kudinov O. Complexity for partial computable functions over computable Polish spaces. Mathematical Structures in Computer Science. 2018 Mar 1;28(3):429-447. doi: 10.1017/S0960129516000438

Author

Korovina, Margarita ; Kudinov, Oleg. / Complexity for partial computable functions over computable Polish spaces. In: Mathematical Structures in Computer Science. 2018 ; Vol. 28, No. 3. pp. 429-447.

BibTeX

@article{252abd2fdce34e85b4c09ffda87f239f,
title = "Complexity for partial computable functions over computable Polish spaces",
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.",
author = "Margarita Korovina and Oleg Kudinov",
year = "2018",
month = mar,
day = "1",
doi = "10.1017/S0960129516000438",
language = "English",
volume = "28",
pages = "429--447",
journal = "Mathematical Structures in Computer Science",
issn = "0960-1295",
publisher = "Cambridge University Press",
number = "3",

}

RIS

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 -

ID: 12177991