Number of Queries: A Measure of Complexity

复杂性理论研究的是问题有多难。Beigel博士的研究解决了以下问题：什么时候解决k+1个问题的实例比只解决k个实例要困难得多？这个问题的答案并不明显，因为解决n个实例并不比解决1个实例难多少。最近，各种各样的研究人员都在研究为了解决一个问题而必须对oracle进行的查询数量，以此来衡量该问题的难度。统计oracle查询提供了一种形式化本研究中提出的主要问题的方法，并自然地导致了可欺骗集、p- terse集和p-超terse集的定义。对这些集合的研究使我们有可能证明解决某些重要问题的k+1个实例比解决k个实例要困难得多。Beigel博士也在研究这些概念与复杂性理论中其他重要概念的关系。

Complexity theory deals with how hard problems are. Dr. Beigel's research addresses the following question: When is it significantly harder to solve k+1 instances of a problem than to solve only k instances? The answer to this question is not obvious because there are hard problems for which solving n instances is not much harder than solving 1 instance. Recently, various researchers have looked at the number of queries that must be made to an oracle in order to solve a problem as a measure of that problem's difficulty. Counting oracle queries provides a way of formalizing the main question posed in this research and leads naturally to the definition of cheatable sets, p- terse sets, and p-superterse sets. The study of these sets makes it possible to prove that it is significantly harder to solve k+1 instances of certain kinds of important problems than k instances. Dr. Beigel is also investigating how these notions are related to other important concepts in complexity theory.