Please use this identifier to cite or link to this item:
Title: Infinitely-often autoreducible sets
Authors: Beigel, R.
Fortnow, L.
Stephan, F. 
Keywords: Algorithmic randomness
Autoreducible sets
Computational complexity
Exponential-time computable sets
Infinitely-often autoreducible sets
Issue Date: 2006
Citation: Beigel, R., Fortnow, L., Stephan, F. (2006). Infinitely-often autoreducible sets. SIAM Journal on Computing 36 (3) : 595-608. ScholarBank@NUS Repository.
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
ISSN: 00975397
DOI: 10.1137/S0097539704441630
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 10, 2018


checked on Dec 10, 2018

Page view(s)

checked on Dec 7, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.