Please use this identifier to cite or link to this item: https://doi.org/10.1137/S0097539704441630
Title: Infinitely-often autoreducible sets
Authors: Beigel, R.
Fortnow, L.
Stephan, F. 
Keywords: Algorithmic randomness
Autoreducible sets
Computational complexity
Exponential-time computable sets
Hausdorff-dimension
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. 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
URI: http://scholarbank.nus.edu.sg/handle/10635/103424
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.

SCOPUSTM   
Citations

2
checked on Aug 16, 2018

WEB OF SCIENCETM
Citations

2
checked on Jul 23, 2018

Page view(s)

25
checked on Jun 1, 2018

Google ScholarTM

Check

Altmetric


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