Effective Search Problems

✍ Scribed by Martin Kummer; Frank Stephan

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 734 KB
• Volume: 40
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19940400209

✦ Synopsis

Abstract

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective.

Mathematics Subject Classification: 03D20, 68Q15, 68R05.