{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:17:58Z","timestamp":1725560278606},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281931"},{"type":"electronic","value":"9783540318736"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_42","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T14:00:06Z","timestamp":1127829606000},"page":"479-490","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Semilinear Problems in Succinct Representation"],"prefix":"10.1007","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulin Jacob\u00e9","family":"de Naurois","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","first-page":"231","volume":"6","author":"S.I. Adian","year":"1957","unstructured":"Adian, S.I.: Unsolvability of certain algorithmic problems in the theory of groups. Trudy Moskov. Math. Obshch.\u00a06, 231\u2013298 (1957) (in Russian)","journal-title":"Trudy Moskov. Math. Obshch."},{"key":"42_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Heidelberg (1998)"},{"key":"42_CR3","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539702415950","volume":"33","author":"P. B\u00fcrgisser","year":"2004","unstructured":"B\u00fcrgisser, P., Cucker, F.: Counting complexity classes for numeric computations I: Semilinear sets. SIAM J. Comp.\u00a033, 227\u2013260 (2004)","journal-title":"SIAM J. Comp."},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"Chandra, A., Stockmeyer, L., Vishkin, U.: Constant depth reducibility. SIAM J. Comp.\u00a013, 423\u2013439 (1984)","journal-title":"SIAM J. Comp."},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jcom.1995.1018","volume":"11","author":"F. Cucker","year":"1995","unstructured":"Cucker, F., Koiran, P.: Computing over the reals with addition and order: Higher complexity classes. Journal of Complexity\u00a011, 358\u2013376 (1995)","journal-title":"Journal of Complexity"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"Fournier, H., Koiran, P.: Are lower bounds easier over the reals? In: Proc. 30th ACM STOC, pp. 507\u2013513 (1998)","DOI":"10.1145\/276698.276864"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Exact Analysis of Dodgson Elections: Lewis Carroll\u2019s 1876 Voting System is Complete for Parallel Access to NP. Journal of the ACM, 806\u2013825 (1997)","DOI":"10.1145\/268999.269002"},{"key":"42_CR8","first-page":"1093","volume":"244","author":"L.G. Khachijan","year":"1979","unstructured":"Khachijan, L.G.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR\u00a0244, 1093\u20131096 (1979); in Russian, English translation in Soviet Math. Dokl., 20, 191\u2013194 (1979)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"42_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(93)00063-B","volume":"133","author":"P. Koiran","year":"1994","unstructured":"Koiran, P.: Computing over the reals with addition and order. Theoretical Computer Science\u00a0133, 35\u201347 (1994)","journal-title":"Theoretical Computer Science"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"Krentel, M.W.: The complexity of optimization problems. In: Proc. 18th ACM Symp. on the Theory of Computing, pp. 79\u201386 (1986)","DOI":"10.1145\/12130.12138"},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer","year":"1984","unstructured":"Meyer auf der Heide, F.: A polynomial linear search algorithm for the n-dimensional knapsack problem. J. ACM\u00a031, 668\u2013676 (1984)","journal-title":"J. ACM"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1145\/62.322435","volume":"31","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H.: On the complexity of unique solutions. J. ACM\u00a031, 392\u2013400 (1984)","journal-title":"J. ACM"},{"key":"42_CR13","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"42_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0009651","volume-title":"Theoretical Computer Science","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) GI-TCS 1983. LNCS, vol.\u00a0145, pp. 269\u2013276. Springer, Heidelberg (1982)"},{"issue":"2","key":"42_CR15","doi-asserted-by":"publisher","first-page":"172","DOI":"10.2307\/1969933","volume":"67","author":"M. Rabin","year":"1958","unstructured":"Rabin, M.: Recursive unsolvability of group theoretic problems. Ann. of Math.\u00a067(2), 172\u2013194 (1958)","journal-title":"Ann. of Math."},{"key":"42_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-96200-4","volume-title":"Basic Algebraic Geometry","author":"I.R. Shafarevich","year":"1974","unstructured":"Shafarevich, I.R.: Basic Algebraic Geometry. Springer, Heidelberg (1974)"},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF03025291","volume":"20","author":"S. Smale","year":"1998","unstructured":"Smale, S.: Mathematical problems for the next century. Mathematical Intelligencer\u00a020, 7\u201315 (1998)","journal-title":"Mathematical Intelligencer"},{"key":"42_CR18","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res.\u00a034, 250\u2013256 (1986)","journal-title":"Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T03:49:44Z","timestamp":1553572184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11537311_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}