{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T09:11:09Z","timestamp":1698225069197},"reference-count":22,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":4699,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1994,1]]},"abstract":"Abstract<\/jats:title>The task of computing a function F<\/jats:italic> with the help of an oracle X<\/jats:italic> can be viewed as a search problem where the cost measure is the number of queries to X.<\/jats:italic> We ask for the minimal number that can be achieved by a suitable choice of X<\/jats:italic> and call this quantity the query complexity<\/jats:italic> of F.<\/jats:italic> This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on \u201cBounded query classes\u201d. We introduce a fault tolerant version and relate it with Ulam's game. For many natural classes of functions F<\/jats:italic> we obtain tight upper and lower bounds on the query complexity of F.<\/jats:italic> Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective.<\/jats:p>Mathematics Subject Classification:<\/jats:bold> 03D20, 68Q15, 68R05.<\/jats:p>","DOI":"10.1002\/malq.19940400209","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T17:21:09Z","timestamp":1180200069000},"page":"224-236","source":"Crossref","is-referenced-by-count":13,"title":["Effective Search Problems"],"prefix":"10.1002","volume":"40","author":[{"given":"Martin","family":"Kummer","sequence":"first","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Combinatorial Search. Wiley\u2010Teubner Series in Computer Science","author":"Aigner M.","year":"1988"},{"key":"e_1_2_1_3_2","unstructured":"Beigel R. Query\u2010limited reducibilities. Ph. D. thesis Stanford University Stanford USA 1987."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219035"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90029-8"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90037-7"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1014"},{"key":"e_1_2_1_8_2","unstructured":"Beigel R. W. I.Gasarch andE.Kinber Frequency computation and bounded queries. Manuscript 1993."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023860"},{"key":"e_1_2_1_10_2","first-page":"88","volume-title":"Algebraic Systems","author":"D\u00ebgtev A. N.","year":"1981"},{"key":"e_1_2_1_11_2","article-title":"Extremes in the degrees of inferability","author":"Fortnow L.","journal-title":"Annals Pure Applied Logic."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1991.160245"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.2307\/2275300"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.2307\/1996261"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.2307\/2275299"},{"key":"e_1_2_1_16_2","unstructured":"Kummer M. andF.Stephan Some aspects of frequency computation. Technical Report Nr. 21\/91 Fakult\u00e4t f\u00fcr Informatik Universit\u00e4t Karlsruhe 1991."},{"key":"e_1_2_1_17_2","series-title":"Lecture Notes in Computer Science","first-page":"300","volume-title":"Computer Science Logic, Proceedings","author":"Mundici D.","year":"1990"},{"key":"e_1_2_1_18_2","volume-title":"Classical Recursion Theory","author":"Odifreddi P.","year":"1989"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274739"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90014-8"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90270-P"},{"key":"e_1_2_1_23_2","first-page":"25","article-title":"On frequency computation of functions","volume":"2","author":"Trakhtenbrot B. A.","year":"1963","journal-title":"Algebra i Logika"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19940400209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19940400209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T02:45:35Z","timestamp":1698115535000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19940400209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1002\/malq.19940400209"],"URL":"https:\/\/doi.org\/10.1002\/malq.19940400209","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}