{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:36:39Z","timestamp":1787510199228,"version":"build-2736575974"},"publisher-location":"Berlin\/Heidelberg","reference-count":27,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540508406","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028969","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:28:19Z","timestamp":1133396899000},"page":"1-16","source":"Crossref","is-referenced-by-count":5,"title":["On genuinely time bounded computations"],"prefix":"10.1007","author":[{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0890-5401(88)90031-4","volume":"78","author":"L. Babai","year":"1988","unstructured":"L. Babai,B. Just,F. Meyer auf der Heide, On the limits of computations with the floor function, Information and Computation 78(2), 99\u2013107, 1988.","journal-title":"Information and Computation"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"M.Ben-Or, Lower bounds for algebraic computation trees, 15th ACM-STOC, 80\u201386, 1983.","DOI":"10.1145\/800061.808735"},{"key":"1_CR3","unstructured":"A. Borodin,I.Munro, The computational complexity of algebraic and numeric problems, Elsevier Computer Science Library, 1975."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"L.Blum,M.Shub,S.Smale, On a theory of computation over the real numbers; NP-completeness, recursive functions and universal machines, to appear, FOCS, 1988.","DOI":"10.1109\/SFCS.1988.21955"},{"key":"1_CR5","first-page":"417","volume":"16","author":"D. Dobkin","year":"1975","unstructured":"D. Dobkin,R.L. Lipton, A lower bound of 1\/2n 2 on linear search programs for the knapsack problem, JCSS 16, 417\u2013421, 1975.","journal-title":"JCSS"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"B.Just,F.Meyer auf der Heide,A.Wigderson, On computations with integer division, 5th STACS, 29\u201337, 1988.","DOI":"10.1007\/BFb0035829"},{"key":"1_CR7","unstructured":"M.Karpinski,F.Meyer auf der Heide, On the complexity of genuinely polynomial computations, in preparation, 1988."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"N.Karmakar, A new polynomial time algorithm for linear programming, 16th ACM-STOC, 302\u2013311, 1984.","DOI":"10.1145\/800057.808695"},{"issue":"1","key":"1_CR9","first-page":"191","volume":"20","author":"L.G. Khachiyan","year":"1979","unstructured":"L.G. Khachiyan, A polynomial algorithm for linear programming, Soviet Mathematics Declady 20(1), 191\u2013194, 1979.","journal-title":"Soviet Mathematics Declady"},{"issue":"3","key":"1_CR10","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"F. Meyer auf der Heide, A polynomial linear search algorithm for the n-dimensional knapsack problem, J.ACM 31(3), 668\u2013676, 1984.","journal-title":"J.ACM"},{"issue":"4","key":"1_CR11","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/4221.4250","volume":"32","author":"F. Meyer auf der Heide","year":"1985","unstructured":"F. Meyer auf der Heide, Lower bounds for solving linear Diophantine equations on random access machines, J. ACM 32(4), 929\u2013937, 1985.","journal-title":"J. ACM"},{"key":"1_CR12","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":"F. Meyer auf der Heide, Simulating probabilistic by deterministic algebraic computation trees, TCS 41, 325\u2013330, 1985.","journal-title":"TCS"},{"issue":"3","key":"1_CR13","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. Meyer auf der Heide","year":"1988","unstructured":"F. Meyer auf der Heide, Fast algorithms for n-dimensional restrictions of hard problems, J.ACM 35(3), 740\u2013747, 1988.","journal-title":"J.ACM"},{"key":"1_CR14","first-page":"354","volume":"II","author":"Y.V. Matijasevic","year":"1970","unstructured":"Y.V. Matijasevic, Enumerable Sets are Diophantine, Soviet Mathematical Dok lady II, 354\u2013357, 1970.","journal-title":"Soviet Mathematical Dok lady"},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1137\/0212022","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, Towards a strongly polynomial algorithm for linear programming, SIAM J. Comp. 12, 347\u2013353, 1983.","journal-title":"SIAM J. Comp."},{"key":"1_CR16","volume-title":"Suche in einem Arrangement von Hyperebenen, Diplomarbeit","author":"S. Meiser","year":"1988","unstructured":"S. Meiser, Suche in einem Arrangement von Hyperebenen, Diplomarbeit, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, 1988."},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15, 275\u2013280, 1964.","journal-title":"Proc. Amer. Math. Soc."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"D.C.Oppen, Elementary bounds for Presburger arithmetic, 5th ACM-STOC, 34\u201337, 1973.","DOI":"10.1145\/800125.804033"},{"key":"1_CR19","volume-title":"Combinatorial optimization: algorithms and complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou,K. Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice Hall, Englewood Cliffs, New Jersey, 1982."},{"key":"1_CR20","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1145\/321724.321730","volume":"19","author":"E. Reingold","year":"1972","unstructured":"E. Reingold, On the optimality of some set algorithms, J.ACM 19, 649\u2013659, 1972.","journal-title":"J.ACM"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"A.Sch\u00f6nhage, On the power of random access machines, 6th ICALP, 520\u2013529, 1979.","DOI":"10.1007\/3-540-09510-1_42"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"J.Simon, Division is good, 20th IEEE-FOCS, 411\u2013420, 1979.","DOI":"10.1109\/SFCS.1979.13"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"E.Specker, V.Strassen, Komplexit\u00e4t von Entscheidungsproblemen, Springer Lecture Notes 43, 1976.","DOI":"10.1007\/3-540-07805-3"},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF00571464","volume":"2","author":"V. Strassen","year":"1973","unstructured":"V. Strassen, Berechnung und Programm II, Acta Informatica 2, 64\u201379, 1973.","journal-title":"Acta Informatica"},{"key":"1_CR25","volume-title":"Mathematics, Anniversary of Oberwolfach 1984","author":"V. Strassen","year":"1984","unstructured":"V. Strassen, Algebraische Berechnungskomplexit\u00e4t, Perspectives in Mathematics, Anniversary of Oberwolfach 1984, Birkh\u00e4user Verlag, Basel, 1984."},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J.M. Steele","year":"1982","unstructured":"J.M. Steele, A.C. Yao, Lower bounds for algebraic decision trees, J. of Algorithms 3, 1\u20138, 1982.","journal-title":"J. of Algorithms"},{"key":"1_CR27","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"E. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Oper. Res. 34, 250\u2013256, 1986.","journal-title":"Oper. Res."}],"container-title":["Lecture Notes in Computer Science","STACS 89"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0028969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:15:21Z","timestamp":1586578521000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540508406"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0028969","relation":{},"subject":[]}}