Authors: Richard Beigel, Martin Kummer, and Frank Stephan
Abstract: We study the fine structure of the classification of sets of natural numbers A according to the number of queries which are needed to compute the n-fold characteristic function of A. A complete characterization is obtained, relating the question to finite combinatorics. In order to obtain an explicit description we consider several interesting combinatorial problems.
Download Full Paper