{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T11:16:13Z","timestamp":1648898173582},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1983,6,1]],"date-time":"1983-06-01T00:00:00Z","timestamp":423273600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1983,6]]},"DOI":"10.1007\/bf02218439","type":"journal-article","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T08:33:43Z","timestamp":1128587623000},"page":"181-192","source":"Crossref","is-referenced-by-count":4,"title":["Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model"],"prefix":"10.1007","volume":"23","author":[{"given":"Esko","family":"Ukkonen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02218439_CR1","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D. Dobkin","year":"1978","unstructured":"D. Dobkin and R. Lipton,A lower bound of 1\/2 n 2 on linear search programs for the knapsack problem, J. Comput. System. Sci. 16 (1978), 413\u2013417","journal-title":"J. Comput. System. Sci."},{"key":"BF02218439_CR2","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"D. P. Dobkin","year":"1979","unstructured":"D. P. Dobkin and R.J. Lipton,On the complexity of computations under varying sets of primitives. J. Comput. System Sci. 18 (1979), 86\u201391.","journal-title":"J. Comput. System Sci."},{"key":"BF02218439_CR3","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability. Freeman, San Francisco, 1979."},{"key":"BF02218439_CR4","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp,Reducibility among combinatorial problems. In:Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York-London, 1972, pp. 85\u2013103."},{"key":"BF02218439_CR5","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/S0022-0000(72)80034-5","volume":"6","author":"M. O. Rabin","year":"1972","unstructured":"M. O. Rabin,Proving simultaneous positivity of linear forms. J. Comput. System Sci. 6 (1972), 639\u2013650.","journal-title":"J. Comput. System Sci."},{"key":"BF02218439_CR6","doi-asserted-by":"crossref","unstructured":"E. M. Reingold,Computing the maxima and the median. Proc. 12th Ann. Symp. on Switching and Automata Theory (1971), 216\u2013218.","DOI":"10.1109\/SWAT.1971.9"},{"key":"BF02218439_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/3-540-10843-2_25","volume":"115","author":"M. Snir","year":"1981","unstructured":"M. Snir,Proving lower bounds for linear decision trees. In:Automata, Languages, and Programming, Eighth Colloquium, Acre, July 1981. Springer Lecture Notes in Computer Science 115 (1981), 305\u2013315.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"BF02218439_CR8","doi-asserted-by":"crossref","unstructured":"A. C. Yao,On the parallel computation for the knapsack problem. Proc. 13th Ann. ACM Symp. on Theory of Computing (1981), 123\u2013127.","DOI":"10.1145\/800076.802465"},{"key":"BF02218439_CR9","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1137\/0209028","volume":"9","author":"A. C. Yao","year":"1980","unstructured":"A. C. Yao and R. L. Rivest,On the polyhedral decision problem. SIAM J. on Computing 9 (1980), 343\u2013347.","journal-title":"SIAM J. on Computing"}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02218439.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02218439\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02218439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T04:36:39Z","timestamp":1586493399000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02218439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["BF02218439"],"URL":"https:\/\/doi.org\/10.1007\/bf02218439","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}