Number of Queries: A Measure of Complexity

复杂性理论研究的是问题有多难。 Beigel博士的 研究解决了以下问题： 解决k+1个问题比只解决k个问题更难 实例？ 这个问题的答案并不明显，因为 是很难的问题，解决n个实例并不比 解决1个实例。 最近，各种研究人员研究了 为了解决一个问题，必须向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.