{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:02:33Z","timestamp":1742914953171,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642390524"},{"type":"electronic","value":"9783642390531"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39053-1_1","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T04:28:12Z","timestamp":1370233692000},"page":"1-11","source":"Crossref","is-referenced-by-count":3,"title":["Real Benefit of Promises and Advice"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Brandt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Ziegler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: The Isomorphism Conjecture for $\\mathcal{NP}$. In: Cooper, S.B., Sorbi, A. (eds.) Computability in Context, pp. 19\u201348. World Scientific (2009)","DOI":"10.1142\/9781848162778_0002"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Springer (1997)","DOI":"10.1007\/978-3-662-03338-8"},{"issue":"3","key":"1_CR3","first-page":"320","volume":"209","author":"O. Beyersdorff","year":"2011","unstructured":"Beyersdorff, O., K\u00f6bler, J., M\u00fcller, S.: Proof Systems that Take Advice. Proof Systems that Take Advice\u00a0209(3), 320\u2013332 (2011)","journal-title":"Proof Systems that Take Advice"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(95)00249-9","volume":"162","author":"V. Brattka","year":"1996","unstructured":"Brattka, V.: Recursive Characterization of Computable Real-Valued Functions and Relations. Theoretical Computer Science\u00a0162, 45\u201377 (1996)","journal-title":"Theoretical Computer Science"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(98)00095-4","volume":"210","author":"V. Brattka","year":"1999","unstructured":"Brattka, V.: Computable Invariance. Theoretical Computer Science\u00a0210, 3\u201320 (1999)","journal-title":"Theoretical Computer Science"},{"key":"1_CR6","unstructured":"Braverman, M.: On the Complexity of Real Functions. In: Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 155\u2013164"},{"issue":"3","key":"1_CR7","first-page":"318","volume":"53","author":"M. Braverman","year":"2006","unstructured":"Braverman, M., Cook, S.A.: Computing over the Reals: Foundations for Scientific Computing. Notices of the Americal Mathematical Society\u00a053(3), 318\u2013329 (2006)","journal-title":"Notices of the Americal Mathematical Society"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Brattka, V., Pauly, A.M.: Computation with Advice. In: Electronic Proceedings in Theoretical Computer Science, vol.\u00a024 (June 2010)","DOI":"10.4204\/EPTCS.24.9"},{"key":"1_CR9","unstructured":"Brandt, U., Walter, H.K.-G.: Cohesiveness in Promise Problems. Presented at the 64th GI Workshop on Algorithms and Complexity (2012)"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"Even, S., Selman, A.L., Yacobi, Y.: The Complexity of Promise Problems with Applications to Public-Key Cryptography. Inform. and Control\u00a061, 159\u2013173 (1984)","journal-title":"Inform. and Control"},{"issue":"1","key":"1_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1145\/2455.214111","volume":"32","author":"S. Even","year":"1985","unstructured":"Even, S., Selman, A.L., Yacobi, Y.: Hard-Core Theorems for Complexity Classes. Journal of the ACM\u00a032(1), 205\u2013217 (1985)","journal-title":"Journal of the ACM"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: On Promise Problems: A Survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Shimon Even Festschrift. LNCS, vol.\u00a03895, pp. 254\u2013290. Springer, Heidelberg (2006)","DOI":"10.1007\/11685654_12"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press (2008)","DOI":"10.1017\/CBO9780511804106"},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"61","DOI":"10.4064\/fm-44-1-61-71","volume":"44","author":"A. Grzegorczyk","year":"1957","unstructured":"Grzegorczyk, A.: On the Definitions of Computable Real Continuous Functions. Fundamenta Mathematicae\u00a044, 61\u201377 (1957)","journal-title":"Fundamenta Mathematicae"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L.A., Torenvliet, L.: Theory of Semi-Feasible Algorithms. Springer Monographs in Theoretical Computer Science (2003)","DOI":"10.1007\/978-3-662-05080-4"},{"issue":"4","key":"1_CR16","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1006\/jcom.2002.0648","volume":"18","author":"P. Hertling","year":"2002","unstructured":"Hertling, P.: Topological Complexity of Zero Finding with Algebraic Operations. Journal of Complexity\u00a018(4), 912\u2013942 (2002)","journal-title":"Journal of Complexity"},{"issue":"2","key":"1_CR17","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. Computational Complexity\u00a019(2), 305\u2013332 (2010)","journal-title":"Computational Complexity"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Kawamura, A., Cook, S.A.: Complexity Theory for Operators in Analysis. In: Proc. 42nd Ann. ACM Symp. on Theory of Computing (STOC 2010), pp. 495\u2013502 (2010)","DOI":"10.1145\/1806689.1806758"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Kawamura, A., Cook, S.A.: Complexity Theory for Operators in Analysis. ACM Transactions in Computation Theory\u00a04(2), article 5 (2012)","DOI":"10.1145\/2189778.2189780"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(82)80003-0","volume":"20","author":"K.-I. Ko","year":"1982","unstructured":"Ko, K.-I., Friedman, H.: Computational Complexity of Real Functions. Theoretical Computer Science\u00a020, 323\u2013352 (1982)","journal-title":"Theoretical Computer Science"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Ko, K.-I.: Complexity Theory of Real Functions. Birkh\u00e4user (1991)","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Ko, K.-I.: Polynomial-Time Computability in Analysis. In: Ershov, Y.L., et al. (eds.) Handbook of Recursive Mathematics, vol.\u00a02, pp. 1271\u20131317 (1998)","DOI":"10.1016\/S0049-237X(98)80052-9"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-32589-2_51","volume-title":"Mathematical Foundations of Computer Science 2012","author":"A. Kawamura","year":"2012","unstructured":"Kawamura, A., Ota, H., R\u00f6snick, C., Ziegler, M.: Computational Complexity of Smooth Differential Equations. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 578\u2013589. Springer, Heidelberg (2012)"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Kreisel, G., Macintyre, A.: Constructive Logic versus Algebraization I. In: Troelstra, A.S., van Dalen, D. (eds.) Proc. L.E.J. Brouwer Centenary Symposium, pp. 217\u2013260. North-Holland (1982)","DOI":"10.1016\/S0049-237X(09)70130-2"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Springer (1997)","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(77)90048-2","volume":"5","author":"H. Luckhardt","year":"1977","unstructured":"Luckhardt, H.: A Fundamental Effect in Computations on Real Numbers. Theoretical Computer Science\u00a05, 321\u2013324 (1977)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"1_CR27","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/321892.321895","volume":"22","author":"N. Lynch","year":"1975","unstructured":"Lynch, N.: On Reducibility to Complex or Sparse Sets. Journal of the ACM\u00a022(3), 341\u2013345 (1975)","journal-title":"Journal of the ACM"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(94)00067-0","volume":"133","author":"C. Michaux","year":"1994","unstructured":"Michaux, C.: $\\mathcal{P}\\neq\\mathcal{NP}$ over the Nonstandard Reals Implies $\\mathcal{P}\\neq\\mathcal{NP}$ over \u211d. Theoretical Computer Science\u00a0133, 95\u2013104 (1994)","journal-title":"Theoretical Computer Science"},{"key":"1_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/3-540-16761-7_78","volume-title":"Automata, Languages and Programming","author":"N.T. M\u00fcller","year":"1986","unstructured":"M\u00fcller, N.T.: Subpolynomial Complexity Classes of Real Functions and Real Numbers. In: Kott, L. (ed.) ICALP 1986. LNCS, vol.\u00a0226, pp. 284\u2013293. Springer, Heidelberg (1986)"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/3-540-18088-5_37","volume-title":"Automata, Languages and Programming","author":"N.T. M\u00fcller","year":"1987","unstructured":"M\u00fcller, N.T.: Uniform Computational Complexity of Taylor Series. In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol.\u00a0267, pp. 435\u2013444. Springer, Heidelberg (1987)"},{"key":"1_CR31","unstructured":"M\u00fcller, N.T.: Constructive Aspects of Analytic Functions. In: Proc. Workshop on Computability and Complexity in Analysis (CCA), InformatikBerichte FernUniversit\u00e4t Hagen, vol.\u00a0190, pp. 105\u2013114 (1995)"},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/3-540-45335-0_14","volume-title":"Computability and Complexity in Analysis","author":"N.T.. M\u00fcller","year":"2001","unstructured":"M\u00fcller, N.T.: The iRRAM: Exact Arithmetic in C++. In: Blank, J., Brattka, V., Hertling, P. (eds.) CCA 2000. LNCS, vol.\u00a02064, pp. 222\u2013252. Springer, Heidelberg (2001)"},{"key":"1_CR33","unstructured":"M\u00fcller, N.T., Moiske, B.: Solving Initial Value Problems in Polynomial Time. In: Proc. 22nd JAIIO-PANEL, pp. 283\u2013293 (1993)"},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.entcs.2008.03.011","volume":"202","author":"N.T. M\u00fcller","year":"2008","unstructured":"M\u00fcller, N.T., Zhao, X.: Complexity of Operators on Compact Sets. Electronic Notes Theoretical Computer Science\u00a0202, 101\u2013119 (2008)","journal-title":"Electronic Notes Theoretical Computer Science"},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Springer (1989)","DOI":"10.1007\/978-3-662-21717-7"},{"key":"1_CR36","unstructured":"Specker, E.: The Fundamental Theorem of Algebra in Recursive Analysis. In: Dejon, B., Henrici, P. (eds.) Constructive Aspects of the Fundamental Theorem of Algebra, pp. 321\u2013329. Wiley-Interscience (1969)"},{"key":"1_CR37","unstructured":"Traub, J.F., Wasilkowski, G.W., Wo\u017aniakowski, H.: Information-Based Complexity. Academic Press (1988)"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Weihrauch, K.: Computable Analysis. Springer (2000)","DOI":"10.1007\/978-3-642-56999-9"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.tcs.2004.06.022","volume":"326","author":"M. Ziegler","year":"2004","unstructured":"Ziegler, M., Brattka, V.: Computability in Linear Algebra. Theoretical Computer Science\u00a0326, 187\u2013211 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"1_CR40","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1016\/j.apal.2011.12.030","volume":"163","author":"M. Ziegler","year":"2012","unstructured":"Ziegler, M.: Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability. Annals of Pure and Applied Logic\u00a0163(8), 1108\u20131113 (2012)","journal-title":"Annals of Pure and Applied Logic"}],"container-title":["Lecture Notes in Computer Science","The Nature of Computation. Logic, Algorithms, Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39053-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T19:09:10Z","timestamp":1676315350000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-39053-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390524","9783642390531"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39053-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}