{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T18:02:24Z","timestamp":1784484144016,"version":"3.55.0"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032313478","type":"print"},{"value":"9783032313485","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2027]]},"DOI":"10.1007\/978-3-032-31348-5_9","type":"book-chapter","created":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:18Z","timestamp":1784482158000},"page":"135-149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["What is a\u00a0Polynomial-Time Computable Square-Integrable Function?"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2333-0884","authenticated-orcid":false,"given":"Aras","family":"Bacho","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8180-0311","authenticated-orcid":false,"given":"Svetlana","family":"Selivanova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6734-7875","authenticated-orcid":false,"given":"Martin","family":"Ziegler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,20]]},"reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1137\/0524016","volume":"24","author":"BK Alpert","year":"1993","unstructured":"Alpert, B.K.: A class of bases in l2 for the sparse representations of integral operators. SIAM J. Math. Anal. 24(1), 246\u2013262 (1993)","journal-title":"SIAM J. Math. Anal."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"9_CR3","unstructured":"Bacho, A., Boche, H., Kutyniok, G.: Complexity blowup for solutions of the laplace and the diffusion equation (2023). arXiv:2212.00693"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bacho, A., Ziegler, M.: Second-order parameterizations for the complexity theory of integrable functions. In: Boulier, F., Mou, C., Sadykov, T.M., Vorozhtsov, E.V. (eds.) Computer Algebra in Scientific Computing - Proc. 27th International Workshop, CASC 2025, Dubai, volume 16235 of Lecture Notes in Computer Science, pp. 27\u201346. Springer (2025)","DOI":"10.1007\/978-3-032-09645-6_2"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Boche, H., Grigorescu, A., Schaefer, R.F., Vincent Poor, H.: Characterization of the complexity of computing the capacity of colored Gaussian noise channels. IEEE Trans. Commun. 72(8), 4844\u20134856 (2024)","DOI":"10.1109\/TCOMM.2024.3381705"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"5005","DOI":"10.1109\/TSP.2021.3102826","volume":"69","author":"H Boche","year":"2021","unstructured":"Boche, H., Pohl, V.: Complexity blowup in simulating analog linear time-invariant systems on digital computers. IEEE Trans. Signal Process. 69, 5005\u20135020 (2021)","journal-title":"IEEE Trans. Signal Process."},{"issue":"8","key":"9_CR7","doi-asserted-by":"publisher","first-page":"5561","DOI":"10.1109\/TIT.2022.3172837","volume":"68","author":"H Boche","year":"2022","unstructured":"Boche, H., Pohl, V.: On non-detectability of non-computability and the degree of non-computability of solutions of circuit and wave equations on digital computers. IEEE Trans. Inf. Theory 68(8), 5561\u20135578 (2022)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Boche, H., Volker Pohl, H., Poor, V.: Characterization of the complexity of computing the minimum mean square error of causal prediction. IEEE Trans. Inf. Theory 70(9), 6627\u20136638 (2024)","DOI":"10.1109\/TIT.2024.3431695"},{"issue":"4\u20135","key":"9_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/malq.200710004","volume":"53","author":"V Brattka","year":"2007","unstructured":"Brattka, V., Dillhage, R.: Computability of compact operators on computable Banach spaces with bases. Math. Log. Q. 53(4\u20135), 345\u2013364 (2007)","journal-title":"Math. Log. Q."},{"issue":"3","key":"9_CR10","first-page":"318","volume":"53","author":"M Braverman","year":"2006","unstructured":"Braverman, M., Cook, S.A.: Computing over the reals: foundations for scientific computing. Not. AMS 53(3), 318\u2013329 (2006)","journal-title":"Not. AMS"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: Counting Complexity, pp. 81\u2013107. Springer-Verlag, Berlin, Heidelberg (1998)","DOI":"10.1007\/978-1-4612-1872-2_4"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0001-8708(84)90019-7","volume":"53","author":"H Friedman","year":"1984","unstructured":"Friedman, H.: The computational complexity of maximization and integration. Adv. Math. 53, 80\u201398 (1984)","journal-title":"Adv. Math."},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Grzegorczyk, A.: On the definitions of computable real continuous functions. FM 44, 61\u201371 (1957)","DOI":"10.4064\/fm-44-1-61-71"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Hemachandra, L.A., Ogiwara, M.: Is #P closed under subtraction? Curr. Trends Theor. Comput. Sci., 523\u2013536 (1993)","DOI":"10.1142\/9789812794499_0039"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00037-010-0286-0","volume":"19","author":"A Kawamura","year":"2010","unstructured":"Kawamura, A.: Lipschitz continuous ordinary differential equations are polynomial-space complete. Comput. Complex. 19(2), 305\u2013332 (2010)","journal-title":"Comput. Complex."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Kawamura, A., Cook, S.: Complexity theory for operators in analysis. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC \u201910, pp. 495\u2013502. ACM, New York (2010)","DOI":"10.1145\/1806689.1806758"},{"issue":"8","key":"9_CR17","doi-asserted-by":"publisher","first-page":"1437","DOI":"10.1017\/S096012951600013X","volume":"27","author":"A Kawamura","year":"2017","unstructured":"Kawamura, A., Steinberg, F., Ziegler, M.: On the computational complexity of the Dirichlet problem for Poisson\u2019s equation. Math. Struct. Comput. Sci. 27(8), 1437\u20131465 (2017)","journal-title":"Math. Struct. Comput. Sci."},{"key":"9_CR18","unstructured":"Kawamura, A., Thies, H., Ziegler, M.: Average-case polynomial-time computability of Hamiltonian dynamics. In: 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117 of LIPIcs. Leibniz International Proceedings in Informatics, pp. 30:17. Schloss Dagstuhl Leibniz-Zent. Inform, Wadern (2018)"},{"key":"9_CR19","first-page":"15","volume":"24","author":"K-I Ko","year":"1982","unstructured":"Ko, K.-I.: The maximum value problem and NP real numbers. JCSS 24, 15\u201335 (1982)","journal-title":"JCSS"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Ko, K.-I.: Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkh\u00e4user, Boston (1991)","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Ivan, K., Gleb, P., Svetlana, S., Martin, Z.: Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations. J. Complexity, 101727 (2023)","DOI":"10.1016\/j.jco.2022.101727"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Kunkle, D.: Type-2 computability on spaces of integrable functions. MLQ 50(4,5), 417\u2013430 (2004)","DOI":"10.1002\/malq.200310109"},{"key":"9_CR23","unstructured":"Lim, D., Selivanova, S., Ziegler, M.: What is a polynomial-time computable L$$^2$$ function? In: Proceedings of the 17th International Conference Computability and Complexity in Analysis (CCA), Bologna (Italy), pp. 41\u201342 (2020). http:\/\/cca-net.de\/cca2020\/CCA2020Abstracts.pdf"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Lim, D., Ziegler, M.: Quantitative coding and complexity theory of continuous data. J. ACM 72(1), 1\u201339 (2025)","DOI":"10.1145\/3705609"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Park, S., et al.:. Semantics, specification logic, and Hoare logic of exact real computation. Logical Methods Comput. Sci. 20(2) (2024)","DOI":"10.46298\/lmcs-20(2:17)2024"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Pour-El, M.B., Richards, J.I.: A computable ordinary differential equation which possesses no computable solution. Ann. Math. Logic 17, 61\u201390 (1979)","DOI":"10.1016\/0003-4843(79)90021-4"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Pour-El, M.B., Richards, J.I.: The wave equation with computable initial data such that its unique solution is not computable. Adv. Math. 39, 215\u2013239 (1981)","DOI":"10.1016\/0001-8708(81)90001-3"},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer, Berlin (1989)","DOI":"10.1007\/978-3-662-21717-7"},{"issue":"4","key":"9_CR29","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1002\/malq.19970430406","volume":"43","author":"MB Pour-El","year":"1997","unstructured":"Pour-El, M.B., Zhong, N.: The wave equation with computable initial data whose unique solution is nowhere computable. MLQ 43(4), 499\u2013509 (1997)","journal-title":"MLQ"},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Schr\u00f6der, M.: Spaces allowing type-2 complexity theory revisited. MLQ 50(4,5), 443\u2013459 (2004)","DOI":"10.1002\/malq.200310111"},{"key":"9_CR31","doi-asserted-by":"publisher","unstructured":"Schr\u00f6der, M., Steinberg, F., Ziegler, M.: Average-case bit-complexity theory of real functions. In: Kotsireas, I.S., Rump, S.M., Yap, C.K. (eds.) MACIS 2015. LNCS, vol. 9582, pp. 505\u2013519. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-32859-1_43","DOI":"10.1007\/978-3-319-32859-1_43"},{"issue":"3","key":"9_CR32","first-page":"145","volume":"14","author":"E Specker","year":"1949","unstructured":"Specker, E.: Nicht konstruktiv beweisbare S\u00e4tze der Analysis. JSL 14(3), 145\u2013158 (1949)","journal-title":"JSL"},{"key":"9_CR33","doi-asserted-by":"crossref","unstructured":"Florian Steinberg. Complexity theory for spaces of integrable functions. Logical Methods Comput. Sci. 13(3), Paper No. 21, 39 (2017)","DOI":"10.23638\/LMCS-13(3:21)2017"},{"issue":"2","key":"9_CR34","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","volume":"42","author":"AM Turing","year":"1937","unstructured":"Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. LMS 42(2), 230\u2013265 (1937)","journal-title":"LMS"},{"issue":"3","key":"9_CR35","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"9_CR36","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(86)90141-6","volume":"47","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W.: Some observations on the connection between counting and recursion. Theoret. Comput. Sci. 47, 131\u2013147 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR37","doi-asserted-by":"crossref","unstructured":"Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)","DOI":"10.1007\/978-3-642-56999-9"},{"issue":"2","key":"9_CR38","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1112\/S0024611502013643","volume":"85","author":"K Weihrauch","year":"2002","unstructured":"Weihrauch, K., Zhong, N.: Is wave propagation computable or can wave computers beat the Turing machine? LMS 85(2), 312\u2013332 (2002)","journal-title":"LMS"},{"issue":"4","key":"9_CR39","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1002\/malq.19990450403","volume":"45","author":"N Zhong","year":"1999","unstructured":"Zhong, N., Zhang, B.-Y.: $$L^p$$-computability. MLQ 45(4), 449\u2013456 (1999)","journal-title":"MLQ"}],"container-title":["Lecture Notes in Computer Science","Timeless Machines: Computability Across Eras"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31348-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:21Z","timestamp":1784482161000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31348-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"ISBN":["9783032313478","9783032313485"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31348-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]},"assertion":[{"value":"20 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}