{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:43Z","timestamp":1725456763657},"publisher-location":"Berlin\/Heidelberg","reference-count":16,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029630","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"362-368","source":"Crossref","is-referenced-by-count":2,"title":["On the complexity of genuinely polynomial computation"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0890-5401(88)90031-4","volume":"78","author":"L. Babai","year":"1988","unstructured":"Babai, L., Just, B., and Meyer auf der Heide, F., On the Limits of Computation with the Floor Function, Information and Computation 78 (1988), pp. 99\u2013107.","journal-title":"Information and Computation"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Lower Bounds for Algebraic Computation Trees, Proc. 15th ACM STOC (1983), pp. 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"39_CR3","unstructured":"Borodin, A., and Munro, I., The Computational Complexity of Algebraic and Numeric Problems, Elsevier Computer Science Library, 1975."},{"key":"39_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"Cook, S. A., A Taxonomy of Problems with Fast Parallel Algorithms, Information and Control 64 (1985), pp. 2\u201322.","journal-title":"Information and Control"},{"issue":"1","key":"39_CR5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1051\/ita\/1989230101011","volume":"23","author":"B. Just","year":"1989","unstructured":"Just, B., Meyer auf der Heide, F., and Widgerson, A., On Computations with Integer Division, Rairo Theoretical Informatics and Applications 23(1) (1989), pp. 101\u2013111.","journal-title":"Rairo Theoretical Informatics and Applications"},{"key":"39_CR6","unstructured":"Karmakar, N., A New Polynomial Time Algorithm for Linear Programming, Proc. 16th ACM STOC (1984), pp. 302\u2013311."},{"key":"39_CR7","series-title":"Research Report","volume-title":"A Survey of Parallel Algorithms for Shared-Memory Machines","author":"R. M. Karp","year":"1988","unstructured":"Karp, R. M., and Remachandran, V., A Survey of Parallel Algorithms for Shared-Memory Machines, Research Report No. UCB\/CSD 88\/407, University of California, Berkeley (1988); to appear in: Handbook of Theoretical Computer Science, North Holland."},{"key":"39_CR8","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1137\/0212022","volume":"12","author":"N. Meggido","year":"1983","unstructured":"Meggido, N., Towards a Genuinely Polynomial Algorithm for Linear Programming, SIAM J. Comp. 12 (1983), pp. 347\u2013353.","journal-title":"SIAM J. Comp."},{"key":"39_CR9","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"Meyer auf der Heide, F., A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, J. ACM 31 (1984), pp. 668\u2013676.","journal-title":"J. ACM"},{"key":"39_CR10","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(85)90079-9","volume":"41","author":"F. Meyer auf der Heide","year":"1985","unstructured":"Meyer auf der Heide, F., Simulating Probabilistic by Deterministic Algebraic Computation Trees, Theoretical Computer Science 41 (1985), pp. 325\u2013330.","journal-title":"Theoretical Computer Science"},{"key":"39_CR11","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. Meyer auf der Heide","year":"1988","unstructured":"Meyer auf der Heide, F. Fast Algorithms for n-Dimensional Restrictions of Hard Problems, J. ACM 35 (1988), pp. 740\u2013747.","journal-title":"J. ACM"},{"key":"39_CR12","unstructured":"Meyer auf der Heide, F., On Genuinely Time Bounded Computations, Proc. 6th STACS (1988), pp. 1\u201316."},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Sch\u00f6nhage, A., On the Power of Random Access Machines, Proc. 6th ICALP (1979), pp. 520\u2013529.","DOI":"10.1007\/3-540-09510-1_42"},{"key":"39_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J. M. Steele","year":"1982","unstructured":"Steele, J. M., and Yao, A. C., Lower Bounds for Algebraic Decision Trees, J. of Algorithms 3 (1982), pp. 1\u20138.","journal-title":"J. of Algorithms"},{"key":"39_CR15","volume-title":"Perspectives in Mathematics, Anniversary of Oberwolfach 1984","author":"V. Strassen","year":"1984","unstructured":"Strassen, V., Algebraische Berechnungskomplexit\u00e4t, Perspectives in Mathematics, Anniversary of Oberwolfach 1984, Birkh\u00e4user Verlag, Basel, 1984."},{"key":"39_CR16","doi-asserted-by":"crossref","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, Operations Research 34 (1986), pp. 250\u2013256.","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029630.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:59:48Z","timestamp":1607551188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0029630","relation":{},"subject":[]}}