Please use this identifier to cite or link to this item:
|Title:||Infinitely-often autoreducible sets|
Exponential-time computable sets
Infinitely-often autoreducible sets
|Citation:||Beigel, R., Fortnow, L., Stephan, F. (2006). Infinitely-often autoreducible sets. SIAM Journal on Computing 36 (3) : 595-608. ScholarBank@NUS Repository. https://doi.org/10.1137/S0097539704441630|
|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.|
|Source Title:||SIAM Journal on Computing|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 20, 2018
WEB OF SCIENCETM
checked on Apr 18, 2018
checked on May 4, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.