Bounded Queries in Complexity Theory

复杂性理论研究的是问题有多难。 最近各种 研究人员研究了必须进行的查询数量， 一个神谕，以解决一个问题，作为衡量该问题的 困难一个集合是可欺骗的，如果2k个字符串的成员可以被 通过只查询k个字符串来确定。 我们研究结构， 关闭属性，复杂性，和自然性的欺骗和 简洁的布景 我们还将这些概念与其他概念进行了比较， 多项式大小的电路，近可测性和选择性。

Complexity theory deals with how hard problems are. Recently various researchers have looked at the number of queries which must be made to an oracle in order to solve a problem as a measure of that problem's difficulty. A set is cheatable if membership of 2k strings can be determined by querying only k strings. We investigate structure, closure properties, complexity, and naturalness of both cheatable and terse sets. We also compare these notions to other concepts such as polynomial size circuits, near-testability, and-selectivity.