Infinitely-often autoreducible sets

Abstract

A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y ≠ x. Furthermore, A is infinitely-often autoreducible if, for infinitely many x, the value A(x) can be computed by querying A only at places y ≠ x. For all other x, the computation outputs a special symbol to signal that the reduction is undefined. It is shown that for polynomial time Turing and truth-table autoreducibility there are A, B, C in the class EXP of all exponential-time computable sets such that A is not infinitely-often Turing autoreducible, B is Turing autoreducible but not infinitely-often truth-table autoreducible and C is truth-table autoreducible with g(n) + 1 queries but not infinitely-often Turing autoreducible with g(n) queries. Here n is the length of the input, g is nondecreasing, and there exists a polynomial p such that p(n) bounds both the computation time and the value of g at input of length n. Furthermore, connections between notions of infinitely-often autoreducibility and notions of approximability are investigated. The Hausdorff-dimension of the class of sets which are not infinitely-often autoreducible is shown to be 1. © 2006 Society for Industrial and Applied Mathematics.