{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T13:40:10Z","timestamp":1662385210177},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,11,7]],"date-time":"2018-11-07T00:00:00Z","timestamp":1541548800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00037-018-0174-6","type":"journal-article","created":{"date-parts":[[2018,11,7]],"date-time":"2018-11-07T04:39:59Z","timestamp":1541565599000},"page":"437-469","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Interactive proofs and a Shamir-like result for real number computations"],"prefix":"10.1007","volume":"28","author":[{"given":"Martijn","family":"Baartse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Meer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,7]]},"reference":[{"key":"174_CR1","unstructured":"S. Arora & B. Barak (2009). Computational Complexity: A Modern Approach. Cambridge University Press."},{"issue":"3","key":"174_CR2","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/s10208-014-9188-x","volume":"15","author":"M Baartse","year":"2015","unstructured":"Baartse, M., Meer, K.: The PCP theorem for NP over the reals. Foundations of Computational Mathematics 15(3), 651\u2013680 (2015a)","journal-title":"Foundations of Computational Mathematics"},{"key":"174_CR3","doi-asserted-by":"crossref","unstructured":"M. Baartse & K. Meer (2015b). Some results on interactive proofs for real computations. In 11th conference Computability in Europe CiE 2015, Bucharest. Proceedings, A. Beckmann, V. Mitrana & M. Soskova, editors, volume 9136 of LNCS, 107\u2013116. Springer","DOI":"10.1007\/978-3-319-20028-6_11"},{"key":"174_CR4","unstructured":"M. Baartse & K. Meer (2016). Real Interactive Proofs for VPSPACE. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22\u201326, 2016\u2013Krak\u00f3w, Poland, Piotr Faliszewski, Anca Muscholl & Rolf Niedermeier, editors, volume 58 of LIPIcs, 14:1\u201314:13. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-016-3"},{"key":"174_CR5","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jco.2016.11.006","volume":"40","author":"M Baartse","year":"2017","unstructured":"Baartse, M., Meer, K.: An algebraic proof of the real number PCP theorem. Journal of Complexity 40, 34\u201377 (2017)","journal-title":"Journal of Complexity"},{"issue":"4","key":"174_CR6","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10208-010-9062-4","volume":"10","author":"S Basu","year":"2010","unstructured":"Basu, S., Zell, T.: Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem. Foundations of Computational Mathematics 10(4), 429\u2013454 (2010)","journal-title":"Foundations of Computational Mathematics"},{"key":"174_CR7","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub & S. Smale (1998). Complexity and real computation Springer, New York, xvi+453","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"174_CR8","doi-asserted-by":"crossref","unstructured":"L. Blum, M. Shub & S. Smale (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc (N.S.) 21(1), 1\u201346","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"174_CR9","unstructured":"Olivier Chapuis & Pascal Koiran (1999). Saturation and stability in the theory of computation over the reals. Ann. Pure Appl. Logic 99(1\u20133), 1\u201349. ISSN 0168\u20130072"},{"issue":"5","key":"174_CR10","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1093\/comjnl\/36.5.400","volume":"36","author":"F Cucker","year":"1993","unstructured":"Cucker, F.: On the complexity of quantifier elimination: The structural approach. The Computer Journal 36(5), 400\u2013408 (1993)","journal-title":"The Computer Journal"},{"key":"174_CR11","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1016\/j.jco.2007.02.005","volume":"23","author":"F Cucker","year":"2007","unstructured":"Cucker, F., Briquel, I.: A note on parallel and alternating time. Journal of Complexity 23, 594\u2013602 (2007)","journal-title":"Journal of Complexity"},{"key":"174_CR12","first-page":"108","volume":"38","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S.: Interactive Proof Systems. In Computational Complexity Theory, Proc. of Symposia in Applied Mathematics. J. Hartmanis, editor 38, 108\u2013128 (1989)","journal-title":"J. Hartmanis, editor"},{"key":"174_CR13","unstructured":"S. Goldwasser & M. Sipser (1986). Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28\u201330, 1986, Berkeley, California, USA, 59\u201368"},{"key":"174_CR14","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s000370050003","volume":"8","author":"S Ivanov","year":"1999","unstructured":"Ivanov, S., de Rougemont, M.: Interactive Protocols on the reals. Computational Complexity 8, 330\u2013345 (1999)","journal-title":"Computational Complexity"},{"issue":"4","key":"174_CR15","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s00037-009-0269-1","volume":"18","author":"P Koiran","year":"2009","unstructured":"Koiran, P., Perifel, S.: VPSPACE and a transfer theorem over the reals. Computational Complexity 18(4), 551\u2013575 (2009)","journal-title":"Computational Complexity"},{"issue":"4","key":"174_CR16","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM 39(4), 859\u2013868 (1992)","journal-title":"Journal of the ACM"},{"key":"174_CR17","doi-asserted-by":"crossref","unstructured":"G. Malod (2011). Succinct Algebraic Branching Programs Characterizing Non-Uniform Complexity Classes. In Proc. ,18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, Olaf Owe, Martin Steffen & Jan Arne Telle, editors, volume 6914 of Lecture Notes in Computer Science, 205\u2013216. Springer","DOI":"10.1007\/978-3-642-22953-4_18"},{"key":"174_CR18","first-page":"435","volume":"309","author":"C Michaux","year":"1989","unstructured":"Michaux, C.: Une remarque \u00e0 propos des machines sur $$\\mathbb{R}$$ R introduites par Blum, Shub et Smale. C.R. Acad. Sci. Paris 309, 435\u2013437 (1989)","journal-title":"Acad. Sci. Paris"},{"issue":"4","key":"174_CR19","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.2178\/jsl\/1230396913","volume":"73","author":"B Poizat","year":"2008","unstructured":"Poizat, B.: \u00c2 la recherche de la d\u00e9finition de la complexit\u00e9 d'espace pour le calcul des polyn\u00f4mes \u00e0 la mani\u00e8re de Valiant. Journal of Symbolic Logic 73(4), 1179\u20131201 (2008)","journal-title":"Journal of Symbolic Logic"},{"key":"174_CR20","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J Renegar","year":"1992","unstructured":"Renegar, J.: On the computational Complexity and Geometry of the first-order Theory of the Reals, I-III. Journal of Symbolic Computation 13, 255\u2013352 (1992)","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"174_CR21","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM 39(4), 869\u2013877 (1992)","journal-title":"Journal of the ACM"},{"key":"174_CR22","unstructured":"L.J. Stockmeyer & A.R. Meyer (1973). Word problems requiring exponential time. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30-May 2, 1973, Austin, Texas, USA, 1\u20139"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0174-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-018-0174-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0174-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T13:24:40Z","timestamp":1662384280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-018-0174-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,7]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["174"],"URL":"https:\/\/doi.org\/10.1007\/s00037-018-0174-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,7]]},"assertion":[{"value":"28 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}