Institute of Information Science, Academia Sinica

A naive notion of query-optimal programs is a program that would not make unnecessary queries to the external agent. Such queries usually created bottlenecks that slow down the performance of contemporary computing tasks. It will be nice if we can find  query-optimal programs for our applications. Unfortunately,  such wishful thinking may not be realistic as we examine the notion of optimal programs defined in terms of Blum's complexity measure. The well known speed-up theorem states that there exist computable functions that do not have optimal programs. However, we may argue that the query complexity doesn't satisfy  Blum's complexity measure, and this may alter the theoretic result of speed-up phenomena. In this presentation, we first argue that, under the Oracle Turing Machine model, the same speed-up theorem can be obtained as long as the complexity measure satisfies Blum's complexity measure. In other words, the power of oracle queries could not eliminate the classical speed-up phenomena.  Then, we consider the oracle query as a dynamic complexity measure, but we have to characterize the notions of optimal programs in a very different way. We give three notions of query-optimal programs in different strength and argue that the stronger the notion of query-optimal programs is, the more difficult to have query-optimal programs. In other words, with a stronger definition of query-optimal programs, one can prove another speed-up theorem, and conclude that, query-optimal program may not always exist?