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.
