Quantifying the Amount of Verboseness
Richard Beigel, Martin Kummer, Frank Stephan · Information and Computation · 1995
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.