{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T10:07:05Z","timestamp":1648721225621},"reference-count":20,"publisher":"Elsevier","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1016\/s0065-2458(08)60645-2","type":"book-chapter","created":{"date-parts":[[2008,5,30]],"date-time":"2008-05-30T08:21:49Z","timestamp":1212135709000},"page":"215-241","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Problems"],"prefix":"10.1016","author":[{"given":"William","family":"Gasarch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0065-2458(08)60645-2_bib1","doi-asserted-by":"crossref","unstructured":"Bent, S. & John, J. Finding the median requires 2n comparisons. Proc. 17th ACM Symp. on Theory of Computing, 1985","DOI":"10.1145\/22145.22169"},{"key":"10.1016\/S0065-2458(08)60645-2_bib2","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","article-title":"Time bounds for selection","volume":"7","author":"Blum","year":"1973","journal-title":"J. Comput. Syst. Sci"},{"key":"10.1016\/S0065-2458(08)60645-2_bib3","series-title":"Mathematical Developments Arising from Hilbert Problems","year":"1976"},{"key":"10.1016\/S0065-2458(08)60645-2_bib4","doi-asserted-by":"crossref","unstructured":"Cook, S.C. (1971). The complexity of theorem proving procedures. Proc. 3rd ACM Symp. on Theory of Computing, pp. 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"10.1016\/S0065-2458(08)60645-2_bib5","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/S0065-2458(08)60645-2_bib6","doi-asserted-by":"crossref","first-page":"425","DOI":"10.2307\/1970289","article-title":"The decision problem for exponential diophantine equations","volume":"74","author":"Davis","year":"1961","journal-title":"Ann. Math."},{"key":"10.1016\/S0065-2458(08)60645-2_bib7","unstructured":"Dor, D. & Zwick, U. (1995). Selecting the median. Proc. 6th Annual Symp. on Discrete Algorithms"},{"issue":"2","key":"10.1016\/S0065-2458(08)60645-2_bib8","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/322123.322128","article-title":"A counting approach to lower bounds for selection problems","volume":"26","author":"Fussenegger","year":"1979","journal-title":"J. ACM"},{"key":"10.1016\/S0065-2458(08)60645-2_bib9","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0065-2458(08)60645-2_bib10","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibilities among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/S0065-2458(08)60645-2_bib11","series-title":"Sorting and Searching,\u201d Vol. 3 of \u201cThe Art of Computer Programming","author":"Knuth","year":"1973"},{"key":"10.1016\/S0065-2458(08)60645-2_bib12","first-page":"279","article-title":"Enumerable sets are diophantine (Russian)","volume":"191","author":"Matijasevic","year":"1970","journal-title":"Doklady Academy Nauk, SSSR"},{"key":"10.1016\/S0065-2458(08)60645-2_bib13","series-title":"Hilbert's Tenth Problem","author":"Matijasevic","year":"1993"},{"key":"10.1016\/S0065-2458(08)60645-2_bib14","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1145\/4221.4259","article-title":"Applications of Ramsey's theorem to decision tree complexity","volume":"32","author":"Moran","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/S0065-2458(08)60645-2_bib15","series-title":"Elements of the Theory of Computation","author":"Papadimitriou","year":"1981"},{"key":"10.1016\/S0065-2458(08)60645-2_bib16","doi-asserted-by":"crossref","DOI":"10.1145\/361405.361423","article-title":"A sorting problem and its complexity","volume":"15","author":"Pohl","year":"1972","journal-title":"Comm. ACM"},{"key":"10.1016\/S0065-2458(08)60645-2_bib17","doi-asserted-by":"crossref","unstructured":"Pratt, V. & Yao, F.F. (1973). On lower bounds for computing the i -th largest element. Proc. 14th IEEE Symp. on Found. of Comp. Sci., pp. 70\u201381","DOI":"10.1109\/SWAT.1973.18"},{"key":"10.1016\/S0065-2458(08)60645-2_bib18","series-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"10.1016\/S0065-2458(08)60645-2_bib19","article-title":"Finding the median","volume":"13","author":"Schonenhage","year":"1976","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0065-2458(08)60645-2_bib20","series-title":"Recursively Enumerable Sets and Degrees","first-page":"184","author":"Soare","year":"1987"}],"container-title":["Advances in Computers"],"original-title":[],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T18:52:07Z","timestamp":1557600727000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0065245808606452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":20,"URL":"https:\/\/doi.org\/10.1016\/s0065-2458(08)60645-2","relation":{},"ISSN":["0065-2458"],"issn-type":[{"value":"0065-2458","type":"print"}],"subject":[],"published":{"date-parts":[[1996]]}}}