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.
