{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:04:27Z","timestamp":1725663867250},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540527534"},{"type":"electronic","value":"9783540471370"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52753-2_33","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:42:29Z","timestamp":1330206149000},"page":"76-89","source":"Crossref","is-referenced-by-count":0,"title":["The complexity of subtheories of the existential linear theory of reals"],"prefix":"10.1007","author":[{"given":"Elias","family":"Dahlhaus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"5_CR1","first-page":"251","volume":"32","author":"M. Ben'Or","year":"1986","unstructured":"M. Ben'Or, D. Kozen, J. Reif, The complexity of elementary algebra and geometry, JCSS 32 (1986), pp. 251\u2013264.","journal-title":"JCSS"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), pp. 2\u201322.","journal-title":"Information and Control"},{"unstructured":"E. Dahlhaus, Reductions to NP-complete problems by interpretations, Logic and Machines: Decision Problems and Complexity, E. Boerger, G. Hasenjaeger, D. Roedding ed. (1983), LNCS 171, pp.357\u2013365.","key":"5_CR3"},{"doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, Skolem normal forms concerning the least fixpoint operator, Computation Theory and Logic, E. Boerger ed., LNCS 270, pp. 101\u2013106.","key":"5_CR4","DOI":"10.1007\/3-540-18170-9_158"},{"key":"5_CR5","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0020-0190(79)90152-2","volume":"8","author":"D. Dobkin","year":"1979","unstructured":"D. Dobkin, R. Lipton, S. Reiss, Linear programming is log-space hard for P, Information Processing Letters 8 (1979), pp. 96\u201397.","journal-title":"Information Processing Letters"},{"unstructured":"S. Fortune, J. Wyllie,Parallelism in random access machines, 10th STOC (1978), pp. 114\u2013118.","key":"5_CR6"},{"key":"5_CR7","volume-title":"Computers and Intractability","author":"M. Garey","year":"1978","unstructured":", M. Garey, D. Johnson, Computers and Intractability, Freeman and Co., San Francisco, 1978."},{"doi-asserted-by":"crossref","unstructured":"J. v. z. Gathen, M. Sieveking, Weitere zum Erfuellungsproblem aequivalente kombinatorische Aufgaben, Komplexit\u00e4t von Entscheidungsproblemen, E. Specker V. Strassen ed., LNCS 43 (1976).","key":"5_CR8","DOI":"10.1007\/3-540-07805-3_5"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L. Goldschlager","year":"1977","unstructured":", L. Goldschlager, The monotone and the planar circuit value problems are log space complete for P, SIGACT News 9 (1977), pp. 25\u201329.","journal-title":"SIGACT News"},{"key":"5_CR10","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1976","unstructured":"N. Jones, W. Laaser, Complete problems for deterministic polynomial time, TCS 3 (1976), pp. 105\u2013117.","journal-title":"TCS"},{"key":"5_CR11","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmakar","year":"1984","unstructured":"N. Karmakar, A new polynomial time algorithm for linear programming, Combinatorica 4 (1984), pp.373\u2013395.","journal-title":"Combinatorica"},{"key":"5_CR12","first-page":"191","volume":"20","author":"L. Khachiyan","year":"1979","unstructured":"L. Khachiyan, A polynomial time algorithm for linear programming, Soviet Mathematics Doklady 20 (1979), pp.191\u2013194.","journal-title":"Soviet Mathematics Doklady"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, The circuit value problem is logspace complete for P, SIGACT News 7 (1975), pp. 18\u201320.","journal-title":"SIGACT News"},{"doi-asserted-by":"crossref","unstructured":"J. Lassez, K. McAloon, Independence of negative constraints, TAP-SOFT 89, vol. 1, J. Diaz, F. Orejas ed., LNCS 351, pp. 19\u201327.","key":"5_CR14","DOI":"10.1007\/3-540-50939-9_122"},{"key":"5_CR15","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1016\/0196-6774(84)90020-8","volume":"5","author":"T. Lengauer","year":"1984","unstructured":"T. Lengauer, On the solution of inequality systems relevant to IC-layout, Journal of algorithms 5 (1984), pp. 408\u2013421.","journal-title":"Journal of algorithms"},{"unstructured":"G. Lueker, N. Meggido, V. Ramachandran, Linear programming with two variables per inequality in poly-log time, 18 t h STOC (1986), pp. 196\u2013205.","key":"5_CR16"},{"key":"5_CR17","first-page":"547","volume":"23","author":"L. Lov\u00e1sz","year":"1977","unstructured":"L. Lov\u00e1sz, P. G\u00e1cs, Some remarks on generalized spectra, ZML 23 (1977), pp. 547\u2013554.","journal-title":"ZML"},{"unstructured":"A. Schrijver, Disjoint homotopic trees in a planar graph, preprint.","key":"5_CR18"},{"unstructured":"H. Wagener, Parallel computational geometry, exploiting polygonal order for maximally parallel algorithms, Doctoral Dissertation, Technical University of Berlin, Dept. of Computer Science.","key":"5_CR19"},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0747-7171(88)80003-8","volume":"5","author":"V. Weispfenning","year":"1988","unstructured":"V. Weispfenning, The complexity of linear problems in fields, Journal of Symbolic Computation 5 (1988), pp. 3\u201327.","journal-title":"Journal of Symbolic Computation"}],"container-title":["Lecture Notes in Computer Science","CSL '89"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52753-2_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:07Z","timestamp":1605648307000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52753-2_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540527534","9783540471370"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-52753-2_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}