Authors: Richard Beigel, William Gasarch, and Efim Kinber

Abstract: There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: F_A^a(x₁, ... , x_a) = A(x₁)...A(x_a). We are interested in the complexity (in terms of the number of queries) of approximating F_A^a. Let b ≤ a and let f be any function such that F_A^a(x₁, ... , x_a) and f(x₁, ... , x_a) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

Download Full Paper