Bounded Queries in Complexity Theory

复杂性理论研究的是问题有多难。最近，不同的研究人员研究了为了解决一个问题而必须对Oracle进行的查询的数量，以此来衡量该问题的难度。如果可以通过仅查询k个字符串来确定2k个字符串的成员资格，则集合是可欺骗的。我们研究了可欺骗集合和简洁集合的结构、闭包性质、复杂性和自然性。我们还将这些概念与其他概念进行比较，如多项式大小电路、近可测试性和选择性。

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.