Infinitely‐Often Autoreducible Sets
Richard Beigel, Lance Fortnow, Frank Stephan · SIAM Journal on Computing · 2006
A set A is autoreducible if one can compute, for all x, the value $A(x)$ by querying A only at places $y eq 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 eq 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.