The Use of A Reduction
Since every reduction from a set B to a set A has to determine whether a single element is in A in only finitely many steps, it can only make finitely many queries of membership in the set B. When the amount of information about the set B used to compute a single bit of A is discussed, this is made precise by the use function. Formally, the use of a reduction is the function that sends each natural number n to the largest natural number m whose membership in the set B was queried by the reduction while determining the membership of n in A.
Read more about this topic: Turing Reduction
Famous quotes containing the word reduction:
“The reduction of nuclear arsenals and the removal of the threat of worldwide nuclear destruction is a measure, in my judgment, of the power and strength of a great nation.”
—Jimmy Carter (James Earl Carter, Jr.)