Number of Queries: A Measure of Complexity

复杂性理论研究的是问题有多难。Beigel博士的研究解决了以下问题：什么时候解决一个问题的k+1个实例比只解决k个实例要难得多？这个问题的答案并不明显，因为有一些难题，对于这些难题，解决n个实例并不比解决1个实例难多少。最近，不同的研究人员研究了为了解决问题而必须向Oracle进行的查询数量，以此来衡量该问题的难度。计算Oracle查询提供了一种将本研究中提出的主要问题形式化的方法，并自然地导致了可欺骗集、p-简洁集和p-超集的定义。通过对这些集合的研究，可以证明某些重要问题的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.