{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T22:57:39Z","timestamp":1649026659566},"reference-count":39,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T00:00:00Z","timestamp":1482105600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1017\/s0960129516000438","type":"journal-article","created":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T04:25:46Z","timestamp":1482121546000},"page":"429-447","source":"Crossref","is-referenced-by-count":3,"title":["Complexity for partial computable functions over computable Polish spaces"],"prefix":"10.1017","volume":"28","author":[{"given":"MARGARITA","family":"KOROVINA","sequence":"first","affiliation":[]},{"given":"OLEG","family":"KUDINOV","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,12,19]]},"reference":[{"key":"S0960129516000438_ref12","first-page":"455","volume-title":"Logic Colloquium 76","author":"Ershov","year":"1977"},{"key":"S0960129516000438_ref2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn027"},{"key":"S0960129516000438_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"},{"key":"S0960129516000438_ref39","volume-title":"Schriften zur Angew. Math. u. Informatik","author":"Weihrauch","year":"1980"},{"key":"S0960129516000438_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129513000315"},{"key":"S0960129516000438_ref4","first-page":"1418","article-title":"Index sets for classes of high rank structures","volume":"72","author":"Calvert","year":"2007","journal-title":"Journal of Symbolic Computation"},{"key":"S0960129516000438_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.06.007"},{"key":"S0960129516000438_ref30","volume-title":"Degrees of Unsolvability","author":"Shoenfield","year":"1971"},{"key":"S0960129516000438_ref18","volume-title":"Elements of the Theory of Functions and Functional Analysis","author":"Kolmogorov","year":"1999"},{"key":"S0960129516000438_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.011"},{"key":"S0960129516000438_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80030-5"},{"key":"S0960129516000438_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"S0960129516000438_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00052-3"},{"key":"S0960129516000438_ref14","first-page":"755","article-title":"Spectra of high\n                     n\n                   and nonlow\n                     n\n                   degrees","volume":"22","author":"Frolov","year":"2012","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"S0960129516000438_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-008-0065-7"},{"key":"S0960129516000438_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20028-6_33"},{"key":"S0960129516000438_ref22","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn033"},{"key":"S0960129516000438_ref19","first-page":"330","volume-title":"CSL'03","author":"Korovina","year":"2003"},{"key":"S0960129516000438_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_36"},{"key":"S0960129516000438_ref20","doi-asserted-by":"crossref","unstructured":"Korovina M.V. and Kudinov O.V. (2005). Towards computability of higher type continuous data. In: Proceedings CiE'05, Lecture Notes in Computer Science, vol. 3526, Springer-Verlag, 235\u2013241.","DOI":"10.1007\/11494645_30"},{"key":"S0960129516000438_ref27","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/155"},{"key":"S0960129516000438_ref1","volume-title":"Computable Structures and the Hyperarithmetical Hierarchy","author":"Ash","year":"2000"},{"key":"S0960129516000438_ref9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025971406116"},{"key":"S0960129516000438_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-006-0029-0"},{"key":"S0960129516000438_ref28","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"S0960129516000438_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90001-A"},{"key":"S0960129516000438_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0960129516000438_ref33","first-page":"1","article-title":"Hyperprojective hierarchy of qcb\n                  0-space","volume":"4","author":"Selivanov","year":"2014","journal-title":"Journal of Computability"},{"key":"S0960129516000438_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00286-2"},{"key":"S0960129516000438_ref16","volume-title":"Encyclopedia of Mathematics","author":"Hodges","year":"1993"},{"key":"S0960129516000438_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01978567"},{"key":"S0960129516000438_ref35","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1143"},{"key":"S0960129516000438_ref8","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/008\/653176"},{"key":"S0960129516000438_ref25","first-page":"124","article-title":"Borel structures: A brief survey","volume":"41","author":"Montalban","year":"2013","journal-title":"Lecture Notes in Logic"},{"key":"S0960129516000438_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19730191901"},{"key":"S0960129516000438_ref26","doi-asserted-by":"crossref","first-page":"215","DOI":"10.4064\/fm-55-3-215-238","article-title":"Recursive metric spaces","volume":"55","author":"Moschovakis","year":"1964","journal-title":"Fundamenta Mathematicae"},{"key":"S0960129516000438_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.08.020"},{"key":"S0960129516000438_ref24","first-page":"201","volume-title":"Lecture Notes in Computer Science","author":"Korovina","year":"2015"},{"key":"S0960129516000438_ref36","doi-asserted-by":"publisher","DOI":"10.2307\/2586596"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129516000438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T15:40:25Z","timestamp":1555342825000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129516000438\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,19]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["S0960129516000438"],"URL":"https:\/\/doi.org\/10.1017\/s0960129516000438","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,19]]}}}