中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

Does the Query-Optimal Program Exist?

:::

Does the Query-Optimal Program Exist?

  • 講者李中志 教授 (School of Information Technology, Illinois State University, USA)
    邀請人:鐘楷閔
  • 時間2014-07-09 (Wed.) 10:30 ~ 12:00
  • 地點資訊所新館106演講廳
摘要

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?